我把每天的持股状态分为四种,那么每天的收益情况就分为四种,这里就用二维dp数组来保存了 dp[i][j],i为天数,j为每天的状态 dp[i][j]各状态存最大收益
class Solution {
public int maxProfit(int[] prices) {
final int len = prices.length;
//没有买卖机会
if (len <=1){
return 0;
}
//每天的持股状态dp[i][j],i为天数,j当前状态 dp[i][j]各状态存最大收益
// j=0不持股,当天没卖出(本就不持股,之前就卖的)
// j=1不持股,当天卖了
// j=2持股,当天买了(注意由于冷却器存在,当天买了说明前一天没卖)
// j=3持股,当天没买(要么是前一天买的,要么是前一天本就持有的)
int[][] dp=new int[len][4];
//初始化
dp[0][0]=0;//本来就不持有,啥也没干
dp[0][1]=0;//可以理解成第0天买入又卖出,那么第0天就是“不持股且当天卖出了”这个状态了,其收益为0,所以初始化为0是合理的
dp[0][2]=-1*prices[0];//第0天只买入,负收益
dp[0][3]=-1*prices[0];//当前的持股收益,负收益
for (int i = 1; i < len; i++) {
//前一天就不持股
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
//前一天持股的收益+今天卖出的收益
dp[i][1]=Math.max(dp[i-1][2],dp[i-1][3])+prices[i];
//前一天可能不持股(非当天卖的)或者持股
dp[i][2]=Math.max(dp[i-1][0],dp[i-1][3])-prices[i];
//要么是前一天买的,要么是前一天本就持有的
dp[i][3]=Math.max(dp[i-1][2],dp[i-1][3]);
}
return Math.max(Math.max(dp[len-1][0],dp[len-1][1]),Math.max(dp[len-1][2],dp[len-1][3]));
}
}