在一天内买卖股票
我在一次面试中被问到这个问题：
Best Time to Buy and Sell Stock
假设你有一个数组，它的第i个元素是给定股票在第一天的价格。如果你只被允许买一股股票，卖出一股股票，设计一个算法来找到买卖的最佳时间。我能够给出一个O(n)算法。
虽然面试官问了我一个接下来的问题，“买一个，卖一个”的情况是什么，然后是“买一个，卖一个”，这意味着一天有两个交易，最大化利润。我能够给出一个O(n^2)算法。但是面试官说这是可以改进的。有O(n)算法吗？
面试官说，你不能同时买两股。你必须买一个卖出，然后在另一个时间买一个，然后再卖。
回答 3
Stack Overflow用户
发布于 2012-02-09 22:32:47
原始问题的reference中给出的O(n)解决方案为原始数组的每个前缀提供了最佳的“买一卖一”的答案。该算法也可以进行简单的修改，以应对“向后”的情况；即“先卖一后买一”，即从数组向后计算；这相当于对数组的每个后缀都有一个“先买一后卖一”的答案。
现在，在“买，卖，买，卖”的情况下，我们有了一些点(在第一次卖出之后)，我们在数组中的某个地方，比如b。对于这个断点，最好的解决方案是0..b的最佳前缀解决方案和b+1..n的最佳后缀解决方案。最好的“买，卖，买，卖”总体上就是这些最优解决方案中最优的。
因此，要解决O(n)中的"buy，sell，buy，sell“，您可以求解O(n)中的前缀，O(n)中的后缀，然后为每个断点计算最佳- So nO(1)。这是一个使用O(n)空间的O(n)算法。
Stack Overflow用户
发布于 2012-12-25 06:42:05
它可以优化为只有一个for循环，但其思想基本上是相同的：
int maxProfit(vector<int> &prices) {
if (prices.empty()) return 0;
int n = prices.size();
int lHolding = prices[0], rHolding = prices[n-1];
int lMax = 0, rMax = 0;
vector<int> profit(n);
for (int i = 1; i < n; i++) {
if (prices[i] > lHolding) {
lMax = max(lMax, prices[i] - lHolding);
} else {
lHolding = prices[i];
}
profit[i] += lMax;
int right = n - 1 - i;
if (rHolding > prices[right]) {
rMax = max(rMax, rHolding - prices[right]);
} else {
rHolding = prices[right];
}
profit[right] += rMax;
}
return *max_element(profit.begin(), profit.end());
}Stack Overflow用户
发布于 2012-12-25 08:56:07
我来晚了，但它在这里。首先，borrible给出的解决方案不是很清楚，因为有人可以实现它并获得O(n^2)。这只是通过循环遍历b，对于每个b，计算前缀和后缀，每个前缀和后缀都是O(n)，所以加在一起就是O (n) *(n)，其中(N)来自b=1...n。这意味着结果是O(n^2)。
要实现该描述，使其在O(n)中运行，需要认识到前缀和后缀是独立的，并且可以像Daniel实现的那样单独运行。
这个解决方案的问题是它需要O(n)空间。假设您的股票跟踪是1千兆点(例如，如果您要迭代两年的数据，这是非常常见的)，那么您将导致内存使用量激增。
如果我是面试官，下一个逻辑问题是:是否有可能删除内存要求？
让我试一试。其中大部分只是解决基本的数学问题。
我们有一个数组价格为0...n-1。
在最初的问题中，我们想要找到r，s，0<=r
P= pricess - pricesr
是最大化的。
在新问题中，我们想要找到i，j，k，l，其中0<=i
Q= pricesj-pricesi+pricesl-pricesk
是最大化的。
(假设n>=4，即没有退化的情况，我们可以很容易地处理)
假设我们解决了原来的问题，那么新问题的解决方案可以分为3种情况：
- i=r
- i
- i=r
实际上很容易通过还原荒谬来证明这一点(即假设不是，然后将i或k扰动为r，将j或l扰动为s。这种扰动将增加q，这与最初的假设相矛盾)。
好的，解决方案很简单：
a.在O(n)中找到r，s
b.检查O(n)中的情况1
c.检查O(n)中的情况2
d.检查O(n)中的情况3
e.返回b，c，d的最大值。
实际上，b、c和d可以在n次迭代中执行。总和是2O(N)+ O(1)，这是O(n)。变量的数量也是固定的，所以空间需求是O(1)。
int maxProfit(vector<int> &prices) {
int n = prices.size();
int b, a;
int m1 = 0;
int hb;
b = a = 0;
hb = 0;
for (int i = 1; i < n; i++) {
if (prices[i] < prices[hb]) {
hb = i;
}
if (prices[i] - prices[hb] > m1) {
m1 = prices[i] - prices[hb];
b = hb; a = i;
}
}
int before = 0, after = 0;
if (b > 0) {
int bb, ba;
before = 0;
int bhb;
bb = ba = 0;
bhb = 0;
for (int i = 0; i < b-1; i++) {
if (prices[i] < prices[bhb]) {
bhb = i;
}
if (prices[i] - prices[bhb] > before) {
before = prices[i] - prices[bhb];
bb = bhb; ba = i;
}
}
}
if (a < n) {
int ab, aa;
int ahb;
ab = aa = a+1;
ahb = a+1;
after = 0;
for (int i = a+2; i < n; i++) {
if (prices[i] < prices[ahb]) {
ahb = i;
}
if (prices[i] - prices[ahb] > after) {
after = prices[i] - prices[ahb];
ab = ahb; aa = i;
}
}
}
int hmb = before + m1;
int hma = after + m1;
int hm = max(hmb,hma);
int tm = b;
for (int j = b+1; j < a; j++) {
if (prices[j] > prices[tm]) {
tm = j;
}
m1 = prices[tm] - prices[b] + prices[a] - prices[j];
hm = max(hm,m1);
}
return hm;
}
可能有一些退化的情况我忘记了，但我花了更长的时间来写这个回复，而不是想出简单的解决方案，所以如果有bug，你就得靠自己了。不过，数学计算似乎是可行的，所以它可能是正确的。
https://stackoverflow.com/questions/9212299
复制相似问题
腾讯云开发者
