最佳买卖股票时机含冷冻期

题目:

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

来源：力扣（LeetCode）
链接

思路:

动态规划:将每天的操作分为3种情况,建立状态转移方程,每天的状态分为3种情况(最后一天只有两种情况:休息或者卖出).

状态

• hold:持有股票
• sold:卖出股票
• rest:休息

操作

• sell:卖出
• buy:买入
• do nothing:啥也不做

建立状态转移图:

符号约定:

price[i] 为第i 天股票价格;
hold[i] 为第 i 天选择hold操作;
sold[i] 为第 i 天选择sold操作;
rest[i] 为第 i 天选择rest操作;

建立状态转移方程:

java代码

int hold = Integer.MIN_VALUE; //确保第一天买入一定是从休息转移过来
int sold = 0;
int rest = 0; 

for(int i = 0; i< prices.length ; i++){
    int preHold = hold; 
    hold = Math.max(rest - prices[i], hold);//1.继续买入 2.休息
    rest = Math.max(rest, sold);//1.继续休息 2.卖完股票休息
    sold = preHold + prices[i]; //1.卖出股票
}

//最后一天只有两种选择
return Math.max(rest, sold);//1.休息 2.卖完股票休息

参考文章

最佳买卖股票时机含冷冻期 - 击败 100%