[关闭]
@natsumi 2016-09-30T08:53:39.000000Z 字数 8069 阅读 1533

Best Time to Buy and Sell Stock

Algorithms


参考
http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html
https://discuss.leetcode.com/topic/32288/2ms-java-dp-solution/2

目录

1. Best Time to Buy and Sell Stock I

LeetCode121
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)空间。

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

2. Best Time to Buy and Sell Stock II

LeetCode122
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)。

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

LeetCode中editorial solution
https://leetcode.com/articles/best-time-buy-and-sell-stock-ii/
Approach #2 (Peak Valley Approach) [Accepted]

  1. public int maxProfit2(int[] prices) {
  2. int i = 0;
  3. int valley = prices[0];
  4. int peak = prices[0];
  5. int maxprofit = 0;
  6. while (i < prices.length - 1) {
  7. while (i < prices.length - 1 && prices[i] >= prices[i + 1])
  8. i++;
  9. valley = prices[i];
  10. while (i < prices.length - 1 && prices[i] <= prices[i + 1])
  11. i++;
  12. peak = prices[i];
  13. maxprofit += peak - valley;
  14. }
  15. return maxprofit;
  16. }

3. Best Time to Buy and Sell Stock III

LeetCode123
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天的价格。最多交易两次,手上最多只能持有一支股票,求最大收益。

3.1 方法一

分析:动态规划法。以第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)。

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

3.2 方法二

时间O(n),空间O(1)

  1. public int maxProfit(int[] prices) {
  2. // these four variables represent your profit after executing corresponding transaction
  3. // in the beginning, your profit is 0.
  4. // when you buy a stock ,the profit will be deducted of the price of stock.
  5. int firstBuy = Integer.MIN_VALUE, firstSell = 0;
  6. int secondBuy = Integer.MIN_VALUE, secondSell = 0;
  7. for (int curPrice : prices) {
  8. if (firstBuy < -curPrice) firstBuy = -curPrice; // the max profit after you buy first stock
  9. if (firstSell < firstBuy + curPrice) firstSell = firstBuy + curPrice; // the max profit after you sell it
  10. if (secondBuy < firstSell - curPrice) secondBuy = firstSell - curPrice; // the max profit after you buy the second stock
  11. if (secondSell < secondBuy + curPrice) secondSell = secondBuy + curPrice; // the max profit after you sell the second stock
  12. }
  13. return secondSell; // secondSell will be the max profit after passing the prices
  14. }

4 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次,手上最多只能持有一支股票,求最大收益。

4.1 方法一

分析:特殊动态规划法。传统的动态规划我们会这样想,到第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] , local[i – 1][j] + diff)
global[i][j] = max(global[i – 1][j], local[i][j])

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]。

  1. public static int maxProfit(int k, int[] prices) {//8ms
  2. if (prices.length < 2) return 0;
  3. int days = prices.length;
  4. if (k >= days) return maxProfitII(prices);
  5. int[][] local = new int[days][k + 1];
  6. int[][] global = new int[days][k + 1];
  7. for (int i = 1; i < days; i++) {
  8. int diff = prices[i] - prices[i - 1];
  9. for (int j = 1; j <= k; j++) {
  10. local[i][j] = Math.max(global[i - 1][j - 1], local[i - 1][j] + diff);
  11. global[i][j] = Math.max(global[i - 1][j], local[i][j]);
  12. System.out.print("local&global(" + i + "," + j + "): " + local[i][j] + " " + global[i][j] + "\t");
  13. }
  14. System.out.println();
  15. }
  16. return global[days - 1][k];
  17. }
  18. public static int maxProfitII(int[] prices) {
  19. int maxProfit = 0;
  20. for (int i = 1; i < prices.length; i++) {
  21. if (prices[i] > prices[i - 1]) {
  22. maxProfit += prices[i] - prices[i - 1];
  23. }
  24. }
  25. return maxProfit;
  26. }

这个算法在leetcode上测试是beat 18+%
dicuss中有另一个算法beat 99+%

4.2 方法二

其实是由3.2节引申出来的
时间O(nk),空间O(k)

作者基本没给注释
自己分析一下

  1. public static int maxProfit2(int k, int[] prices) {//2ms
  2. if (k <= 0 || prices == null || prices.length <= 0) return 0;
  3. if (k > prices.length / 2) { // in this case, it's the same problem as Best Time to Buy & Sell Stock II
  4. int max = 0;
  5. for (int i = 0; i < prices.length - 1; i++) {
  6. int diff = prices[i + 1] - prices[i];
  7. max += diff > 0 ? diff : 0;
  8. }
  9. return max;
  10. } else {
  11. int[] buy = new int[k];//buy[j]用来表示第j次买入后的手中的余额
  12. int[] sell = new int[k];//sell[j]用来表示第j次卖出后的手中的余额
  13. Arrays.fill(buy, Integer.MIN_VALUE);
  14. int buffer = 0;// used to avoid duplicate calculation
  15. int tmp = 0;
  16. for (int i = 0; i < prices.length; i++) {
  17. tmp = 0;
  18. for (int j = 0; j < k; j++) {
  19. buffer = tmp - prices[i];//此时tmp是第j次买入前(即第j-1次卖出后)的余额
  20. if (buy[j] < buffer)//若第i天进行买入后余额 > i-1天内完成第j次买入后的余额
  21. buy[j] = buffer;//则买入,修改buy[j]
  22. buffer = buy[j] + prices[i];//计算若以第i天的价格进行第j次卖出后的余额
  23. if (sell[j] < buffer)//若第i天进行第j次卖出后的余额 > i-1天进行j次交易后的余额
  24. sell[j] = buffer;//则卖出,修改sell[j]
  25. tmp = sell[j];
  26. System.out.print("buy&sell(" + i + "," + j + "): " + buy[j] + " " + sell[j] + "\t");
  27. }
  28. System.out.println();
  29. }
  30. return sell[k - 1];
  31. }
  32. }

这道题的两种方法不好理解
打印看看循环中的这些变量

  1. public static void main(String[] args) {
  2. int[] p = {7, 2, 5, 6, 6, 4, 2, 8};
  3. System.out.println(maxProfit(3, p));
  4. System.out.println(maxProfit2(3, p));
  5. }
  1. //括号里是i和j
  2. local&global(1,1): 0 0 local&global(1,2): 0 0 local&global(1,3): 0 0
  3. local&global(2,1): 3 3 local&global(2,2): 3 3 local&global(2,3): 3 3
  4. local&global(3,1): 4 4 local&global(3,2): 4 4 local&global(3,3): 4 4
  5. local&global(4,1): 4 4 local&global(4,2): 4 4 local&global(4,3): 4 4
  6. local&global(5,1): 2 4 local&global(5,2): 4 4 local&global(5,3): 4 4
  7. local&global(6,1): 0 4 local&global(6,2): 4 4 local&global(6,3): 4 4
  8. local&global(7,1): 6 6 local&global(7,2): 10 10 local&global(7,3): 10 10
  9. 10
  10. buy&sell(0,0): -7 0 buy&sell(0,1): -7 0 buy&sell(0,2): -7 0
  11. buy&sell(1,0): -2 0 buy&sell(1,1): -2 0 buy&sell(1,2): -2 0
  12. buy&sell(2,0): -2 3 buy&sell(2,1): -2 3 buy&sell(2,2): -2 3
  13. buy&sell(3,0): -2 4 buy&sell(3,1): -2 4 buy&sell(3,2): -2 4
  14. buy&sell(4,0): -2 4 buy&sell(4,1): -2 4 buy&sell(4,2): -2 4
  15. buy&sell(5,0): -2 4 buy&sell(5,1): 0 4 buy&sell(5,2): 0 4
  16. buy&sell(6,0): -2 4 buy&sell(6,1): 2 4 buy&sell(6,2): 2 4
  17. buy&sell(7,0): -2 6 buy&sell(7,1): 2 10 buy&sell(7,2): 2 10
  18. 10
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注