买卖股票的这几道题很有意思

我理解的buy 和 sell是 状态函数，表示到当天为止，执行，买或者卖操作，累计的最大收益是多少。是我最喜欢的dp系列。

1. 1次交易

1. class Solution {
   
2.     public int maxProfit(int[] prices) {
   
3.         int buy = Integer.MIN_VALUE, sell = 0;
   
4.         for (int i : prices) {
   
5.             buy = Math.max(buy, - i);
   
6.             sell = Math.max(sell, buy + i);
   
7.         }
   
8.         return sell;
   
9.     }
   
10. }

复制代码

2. 无限次交易

1. class Solution {
   
2.     public int maxProfit(int[] prices) {
   
3.         int sell = 0;
   
4.         for (int i = 1; i < prices.length; i++) {
   
5.             sell += Math.max(0, prices[i]-prices[i-1]);
   
6.         }
   
7.         return sell;
   
8.     }
   
9. }

复制代码

3. 2次交易

1. public class Solution {
   
2.     public int maxProfit(int[] prices) {
   
3.         if(prices == null || prices.length < 2) return 0;
   
4.         int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
   
5.         int sell1 = 0, sell2 = 0;
   
6.         for(int i : prices){
   
7.             buy1 = Math.max(buy1, -i);
   
8.             sell1 = Math.max(sell1, buy1 + i);
   
9.             buy2 = Math.max(buy2, sell1 - i);
   
10.             sell2= Math.max(sell2, buy2 + i);
    
11.         }
    
12.         return sell2;
    
13.     }
    
14. }

复制代码

4. k次交易

1. class Solution {
   
2.     public int maxProfit(int k, int[] prices) {
   
3.         int len = prices.length;
   
4.         if (len < 2 || k == 0) return 0;
   
5.         int[] buys = new int[k + 1];
   
6.         int[] sells = new int[k + 1];
   
7.         Arrays.fill(buys, Integer.MIN_VALUE);
   
8.         for (int i : prices) {
   
9.             for (int j = 1; j <=k; j++) {
   
10.                 buys[j] = Math.max(buys[j], sells[j - 1] - i);
    
11.                 sells[j] = Math.max(sells[j], buys[j] + i);
    
12.             }
    
13.         }
    
14.         return sells[k];
    
15.     }
    
16. }

复制代码

5. 冷却时间

1. class Solution {
   
2.     public int maxProfit(int[] prices) {
   
3.         int len = prices.length;
   
4.         int[] buys = new int[len];
   
5.         int[] sells = new int[len];
   
6.         buys[0] = -prices[0];
   
7.         buys[1] = prices[0] > prices[1] ? - prices[1] : - prices[0];
   
8.         sells[1] = prices[0] > prices[1] ? 0 : prices[1] - prices[0];
   
9.         
   
10.         for (int i = 2; i < len; i++) {
    
11.             buys[i] = Math.max(buys[i - 1], sells[i - 2] - prices[i]);
    
12.             sells[i] = Math.max(sells[i - 1] , buys[i - 1] + prices[i]);
    
13.         }
    
14.         return sells[len - 1];
    
15.     }
    
16. }

复制代码

6. 交易费

1. class Solution {
   
2.     public int maxProfit(int[] prices, int fee) {
   
3.         int sell = 0, buy = Integer.MIN_VALUE;
   
4.         for (int i : prices) {
   
5.             buy = Math.max(buy, sell - i);
   
6.             sell = Math.max(sell, buy + i - fee);

复制代码

胖迪，k次交易那个可以优化.
k / 2 >= prices.length ? Stock 2 : 继续往下走;

可以把复杂度从O(kn)降到O(n)

k次交易这个代码真心不错

我也最喜欢打炮了

总结的很好，非常感谢！

哈哈哈哈胖迪好可爱