188. 买卖股票的最佳时机 IV
思路
四种状态 当天买入, 不买, 卖出, 不卖，状态转移方程
buy[i] = max(buy[i], sell[i-1] - prices) //buy[i]代表第i笔买入自己还剩的钱 买入则减去当天的价格
sell[i] = max(sell[i], buy[i] + prices[i]) //sell[i]代表第i笔卖出后自己还剩的钱 卖出即加入当天的价格
参考代码
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices == null || prices.length == 0) return 0;
if (k >= prices.length / 2){
int res = 0;
for (int i = 1; i < prices.length; i++)
res += Math.max(0, prices[i] - prices[i-1]);
return res;
}
int []buy = new int[k+1];
int []sell = new int[k+1];
Arrays.fill(buy, Integer.MIN_VALUE);
for(int i = 0;i < prices.length; i++){
for (int j = 0; j < k; j++) {
buy[j+1] = Math.max(buy[j+1], sell[j] - prices[i]);
sell[j+1] = Math.max(buy[j+1] + prices[i], sell[j+1]);
}
}
return sell[k];
}
}
