一. 题目
二. 思路--动态规划
我把每天的持股状态分为四种,那么每天的收益情况就分为四种,这里就用二维dp数组来保存了 dp[i][j],i为天数,j为每天的状态 dp[i][j]各状态存最大收益
- j=0不持股,当天没卖出(说明本就不持股,前面就卖了)
- j=1不持股,当天卖了(前一天是持股状态)
- j=2持股,当天买了(前一天持股,为什么这里没有前一天没持股且没卖?因为由于冷却器存在,当天买了说明前一天没卖)
- j=3持股,当天没买(要么是前一天买的,要么是前一天本就持有的)
三. 代码:
代码语言：javascript复制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]));
}
}
