题解 | JAVA #买卖股票的最好时机(四)# [P0-T2]

就是三的解法loop个k遍。

profit[k,i]: k次买卖都在0～i天内执行，在第i天手上钱的最大值。
对于每个k，profit需要分两部计算 (i.e. buy and sell).

例子, k = 3
price:      3  16  6  14  10  19
pass1-buy:  -3 -3  -3 -3  -3  -3
pass1-sell: 0  13  13 13  13  16  <- profit[1, i]
pass2-buy:  -3 -3  7  7   7   7
pass2-sell: 0  13  13 21  21  26  <- profit[2, i], 这个就是(三)的解
pass3-buy:  -3 -3  7  7   11  11
pass3-sell: 0  13  13 21  21  30  <- profit[3, i]

三次操作：3买16卖，6买14卖, 10买19卖， 盈利13+8+9=30

时间O(nk)
空间O(n)

import java.util.*;

public class Solution {
    public int maxProfit (int[] prices, int k) {
      if (prices.length <= 1) return 0;
      
      int[] cash = new int[prices.length];
      for (int i = 0; i < k; i++) {
        maxProfitOnePass(prices, cash);
      }

      return cash[cash.length-1];
    }
  
    public void maxProfitOnePass(int[] prices, int[] cash) {
      // 买
      int maxCash = Integer.MIN_VALUE;
      for (int i = 0; i < cash.length; i++) {
        cash[i] = Math.max(maxCash, cash[i] - prices[i]);
        maxCash = Math.max(maxCash, cash[i]);
      }
      
      // 卖
      maxCash = Integer.MIN_VALUE;
      for (int i = 0; i < cash.length; i++) {
        cash[i] = Math.max(maxCash, cash[i] + prices[i]);
        maxCash = Math.max(maxCash, cash[i]);
      }
    }
}