[Leetcode 动态规划]买卖股票

小灰灰 2022-06-08 08:59 178阅读 0赞

转自http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html

## Best Time to Buy and Sell Stock I  Description: Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find   the maximum profit.  题意：用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。 如果只允许进行一次交易，也就是说只允许买一支股票并卖掉，求最大的收益。  分析：动态规划法。从前向后遍历数组，记录当前出现过的最低价格，作为买入价格，并计算以当天价格出售的收益，作为可能的最大收益，整个遍历过程中，出现过的最大收益就是所求。  代码：O(n)时间，O(1)空间。  **\[cpp\]** [view plain][] [copy][view plain]  **public****class** Solution \{   **public****int** maxProfit(**int**\[\] prices) \{   **if** (prices.length < 2) **return** 0;   **int** maxProfit = 0;   **int** curMin = prices\[0\];   **for** (**int** i = 1; i < prices.length; i++) \{    curMin = Math.min(curMin, prices\[i\]);    maxProfit = Math.max(maxProfit, prices\[i\] - curMin);    \}   **return** maxProfit;    \}   \}  ##

## Best Time to Buy and Sell Stock II ##

Description: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题目：用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。交易次数不限，但一次只能交易一支股票，也就是说手上最多只能持有一支股票，求最大收益。

分析：贪心法。从前向后遍历数组，只要当天的价格高于前一天的价格，就算入收益。

代码：时间O(n)，空间O(1)。

**\[cpp\]** [view plain][] [copy][view plain]

1.  **public****class** Solution \{ 
2.  **public****int** maxProfit(**int**\[\] prices) \{ 
3.  **if** (prices.length < 2) **return** 0; 
4.  
5.  **int** maxProfit = 0; 
6.  **for** (**int** i = 1; i < prices.length; i++) \{ 
7.  **int** diff = prices\[i\] - prices\[i - 1\]; 
8.  **if** (diff > 0) \{ 
9.   maxProfit += diff; 
10.  \} 
11.  \} 
12. 
13. **return** maxProfit; 
14.  \} 
15. \}

## Best Time to Buy and Sell Stock III ##

Description: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题意：用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。最多交易两次，手上最多只能持有一支股票，求最大收益。

分析：动态规划法。以第i天为分界线，计算第i天之前进行一次交易的最大收益preProfit\[i\]，和第i天之后进行一次交易的最大收益postProfit\[i\]，最后遍历一遍，max\{preProfit\[i\] + postProfit\[i\]\} (0≤i≤n-1)就是最大收益。第i天之前和第i天之后进行一次的最大收益求法同Best Time to Buy and Sell Stock I。

代码：时间O(n)，空间O(n)。

**\[cpp\]** [view plain][] [copy][view plain]

1.  **public****class** Solution \{ 
2.  **public****int** maxProfit(**int**\[\] prices) \{ 
3.  **if** (prices.length < 2) **return** 0; 
4.  
5.  **int** n = prices.length; 
6.  **int**\[\] preProfit = **new****int**\[n\]; 
7.  **int**\[\] postProfit = **new****int**\[n\]; 
8.  
9.  **int** curMin = prices\[0\]; 
10. **for** (**int** i = 1; i < n; i++) \{ 
11.  curMin = Math.min(curMin, prices\[i\]); 
12.  preProfit\[i\] = Math.max(preProfit\[i - 1\], prices\[i\] - curMin); 
13.  \} 
14. 
15. **int** curMax = prices\[n - 1\]; 
16. **for** (**int** i = n - 2; i >= 0; i--) \{ 
17.  curMax = Math.max(curMax, prices\[i\]); 
18.  postProfit\[i\] = Math.max(postProfit\[i + 1\], curMax - prices\[i\]); 
19.  \} 
20. 
21. **int** maxProfit = 0; 
22. **for** (**int** i = 0; i < n; i++) \{ 
23.  maxProfit = Math.max(maxProfit, preProfit\[i\] + postProfit\[i\]); 
24.  \} 
25. 
26. **return** maxProfit; 
27.  \} 
28. \}

## Best Time to Buy and Sell Stock IV ##

Description: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题意：用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。最多交易k次，手上最多只能持有一支股票，求最大收益。

分析：特殊动态规划法。传统的动态规划我们会这样想，到第i天时进行j次交易的最大收益，要么等于到第i-1天时进行j次交易的最大收益（第i天价格低于第i-1天的价格），要么等于到第i-1天时进行j-1次交易，然后第i天进行一次交易（第i天价格高于第i-1天价格时）。于是得到动规方程如下（其中diff = prices\[i\] – prices\[i – 1\]）：

> profit\[i\]\[j\] = max(profit\[i – 1\]\[j\], profit\[i – 1\]\[j – 1\] + diff)

看起来很有道理，但其实不对，为什么不对呢？因为diff是第i天和第i-1天的差额收益，如果第i-1天当天本身也有交易呢（也就是说第i-1天刚卖出了股票，然后又买入等到第i天再卖出），那么这两次交易就可以合为一次交易，这样profit\[i – 1\]\[j – 1\] + diff实际上只进行了j-1次交易，而不是最多可以的j次，这样得到的最大收益就小了。

那么怎样计算第i天进行交易的情况的最大收益，才会避免少计算一次交易呢？我们用一个局部最优解和全局最有解表示到第i天进行j次的收益，这就是该动态规划的特殊之处。

我们定义local\[i\]\[j\]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global\[i\]\[j\]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。它们的递推式为（其中diff = prices\[i\] – prices\[i – 1\]）：  
local\[i\]\[j\] = max(global\[i - 1\]\[j - 1\] + max(diff, 0), local\[i - 1\]\[j\] + diff)  
global\[i\]\[j\] = max(local\[i\]\[j\], global\[i - 1\]\[j\])，  
其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值，和前一天的局部最优加上差值后相比，两者之中取较大值，而全局最优比较局部最优和前一天的全局最优。

local\[i\]\[j\]和global\[i\]\[j\]的区别是：local\[i\]\[j\]意味着在第i天一定有交易（卖出）发生，当第i天的价格高于第i-1天（即diff > 0）时，那么可以把这次交易（第i-1天买入第i天卖出）跟第i-1天的交易（卖出）合并为一次交易，即local\[i\]\[j\]=local\[i-1\]\[j\]+diff；当第i天的价格不高于第i-1天（即diff<=0）时，那么local\[i\]\[j\]=global\[i-1\]\[j-1\]+diff，而由于diff<=0，所以可写成local\[i\]\[j\]=global\[i-1\]\[j-1\]。global\[i\]\[j\]就是我们所求的前i天最多进行k次交易的最大收益，可分为两种情况：如果第i天没有交易（卖出），那么global\[i\]\[j\]=global\[i-1\]\[j\]；如果第i天有交易（卖出），那么global\[i\]\[j\]=local\[i\]\[j\]。

参考：http://www.cnblogs.com/grandyang/p/4295761.html

代码：时间O(nk)，空间O(nk)。

**\[cpp\]** [view plain][] [copy][view plain]

1.  **public****class** Solution \{ 
2.  **public****int** maxProfit(**int** k, **int**\[\] prices) \{ 
3.  **if** (prices.length < 2) **return** 0; 
4.  
5.  **int** days = prices.length; 
6.  **if** (k >= days) **return** maxProfit2(prices); 
7.  
8.  **int**\[\]\[\] local = **new****int**\[days\]\[k + 1\]; 
9.  **int**\[\]\[\] global = **new****int**\[days\]\[k + 1\]; 
10. 
11. **for** (**int** i = 1; i < days ; i++) \{ 
12. **int** diff = prices\[i\] - prices\[i - 1\]; 
13. 
14. **for** (**int** j = 1; j <= k; j++) \{ 
15.  local\[i\]\[j\] = Math.max(global\[i - 1\]\[j - 1\], local\[i - 1\]\[j\] + diff); 
16.  global\[i\]\[j\] = Math.max(global\[i - 1\]\[j\], local\[i\]\[j\]); 
17.  \} 
18.  \} 
19. 
20. **return** global\[days - 1\]\[k\]; 
21.  \} 
22. 
23. 
24. **public****int** maxProfit2(**int**\[\] prices) \{ 
25. **int** maxProfit = 0; 
26. 
27. **for** (**int** i = 1; i < prices.length; i++) \{ 
28. **if** (prices\[i\] > prices\[i - 1\]) \{ 
29.  maxProfit += prices\[i\] - prices\[i - 1\]; 
30.  \} 
31.  \} 
32. 
33. **return** maxProfit; 
34.  \} 
35. \}

我们知道，动规所用的二维辅助数组可以降为一维的，即只用大小为k的一维数组记录到达第i天时的局部最优解和全局最优解。需要注意的是，由于第i天时交易k次的最优解依赖于第i-1天时交易k-1次的最优解，所以数组更新应当从后往前（即从k到1）更新。

代码：时间O(nk)，空间O(k)。

**\[cpp\]** [view plain][] [copy][view plain]

1.  **public****class** Solution \{ 
2.  **public****int** maxProfit(**int** k, **int**\[\] prices) \{ 
3.  **if** (prices.length < 2) **return** 0; 
4.  **if** (k >= prices.length) **return** maxProfit2(prices); 
5.  
6.  **int**\[\] local = **new****int**\[k + 1\]; 
7.  **int**\[\] global = **new****int**\[k + 1\]; 
8.  
9.  **for** (**int** i = 1; i < prices.length ; i++) \{ 
10. **int** diff = prices\[i\] - prices\[i - 1\]; 
11. 
12. **for** (**int** j = k; j > 0; j--) \{ 
13.  local\[j\] = Math.max(global\[j - 1\], local\[j\] + diff); 
14.  global\[j\] = Math.max(global\[j\], local\[j\]); 
15.  \} 
16.  \} 
17. **return** global\[k\]; 
18.  \} 
19. 
20. **public****int** maxProfit2(**int**\[\] prices) \{ 
21. **int** maxProfit = 0; 
22. 
23. **for** (**int** i = 1; i < prices.length; i++) \{ 
24. **if** (prices\[i\] > prices\[i - 1\]) \{ 
25.  maxProfit += prices\[i\] - prices\[i - 1\]; 
26.  \} 
27.  \} 
28. **return** maxProfit; 
29.  \} 
30. \}

补充：这道题还有一个陷阱，就是当k大于天数时，其实就退化成 Best Time to Buy and Sell Stock II 了。 另外，Best Time to Buy and Sell Stock III 就是本题k=2的情况，所以说IV是II和III的综合。

309. Best Time to Buy and Sell Stock with Cooldown

在第二题（次数不限）的基础上，卖完股票的转天不能买。求最大收益。

分析：http://www.cnblogs.com/grandyang/p/4997417.html

维护三个一维数组buy, sell，和rest。其中：  
buy\[i\]表示在第i天之前最后一个操作是买，此时的最大收益。  
sell\[i\]表示在第i天之前最后一个操作是卖，此时的最大收益。  
rest\[i\]表示在第i天之前最后一个操作是冷冻期，此时的最大收益。  
我们写出递推式为：

**\[cpp\]** [view plain][] [copy][view plain]

1.  buy\[i\] = max(rest\[i-1\] - price, buy\[i-1\]) 
2.  sell\[i\] = max(buy\[i-1\] + price, sell\[i-1\]) 
3.  rest\[i\] = max(sell\[i-1\], buy\[i-1\], rest\[i-1\])

上述递推式很好的表示了在买之前有冷冻期，买之前要卖掉之前的股票。一个小技巧是如何保证\[buy, rest, buy\]的情况不会出现，这是由于buy\[i\] <= rest\[i\]， 即rest\[i\] = max(sell\[i-1\], rest\[i-1\])，这保证了\[buy, rest, buy\]不会出现。  
另外，由于冷冻期的存在，我们可以得出rest\[i\] = sell\[i-1\]，这样，我们可以将上面三个递推式精简到两个：

**\[cpp\]** [view plain][] [copy][view plain]

1.  buy\[i\] = max(sell\[i-2\] - price, buy\[i-1\]) 
2.  sell\[i\] = max(buy\[i-1\] + price, sell\[i-1\])

由于i只依赖于i-1和i-2，所以我们可以在O(1)的空间复杂度完成算法:

**\[cpp\]** [view plain][] [copy][view plain]

1.  pre\_buy = buy;【因为buy是上一轮的，此句含义：pre\_buy = buy\[i-1\]】 
2.  buy = max(pre\_buy, pre\_sell - prices\[i\]);【此句含义：buy\[i\]即buy = max（buy\[i-1\]即pre\_buy，sell\[i-2\]【尚未更新的即上一轮的pre\_sell】 - prices\[i\]）】 
3.  pre\_sell = sell;【因为sell是上一轮的，此句含义：sell\[i-1\] = sell】 
4.  sell = max(pre\_sell, pre\_buy + prices\[i\]);【此句含义：sell\[i\]即sell = max（sell\[i-1\]即pre\_sell，buy\[i-1\]【已更新为pre\_buy了】 + prices\[i\]）】

参见代码如下：

**\[cpp\]** [view plain][] [copy][view plain]

1.  **class** Solution \{ 
2.  **public**: 
3.  **int** maxProfit(vector<**int**>& prices) \{ 
4.  **int** n = prices.size(); 
5.  **if**(n == 0) **return** 0; 
6.  
7.  **int** buy = 0x80000000, sell = 0, pre\_buy = 0, pre\_sell = 0; 
8.  **for**(**int** i = 0; i < n; ++i) \{ //把buy初值设为-prices\[0\]，for循环从i = 1开始，也对！
9.   pre\_buy = buy; 
10.  buy = max(pre\_buy, pre\_sell - prices\[i\]); 
11.  pre\_sell = sell; 
12.  sell = max(pre\_sell, pre\_buy + prices\[i\]); 
13.  \} 
14. **return** sell; 
15.  \} 
16. \};

[view plain]: http://blog.csdn.net/dr_unknown/article/details/51939121#