309. 最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
解题思路
定义三个数组表示持有当前下标 i 的股票的利润, 卖出利润, 买进利润, 然后进行迭代。迭代的策略可以用状态机来表示。
根据上面的状态机, 可以写出如下的动态规划代码：
public int maxProfit(int[] prices) {
// 持有第i支股票 (即可买进, 也可休息继续持有)
int[] hold = new int[prices.length+1];
// 卖出第i支股票
int[] sold = new int[prices.length+1];
// 既不买进, 也不卖出(处于冷却期状态)
int[] rest = new int[prices.length+1];
// 第一天要么是买进, 要么什么也不做。
hold[0] = Integer.MIN_VALUE;
for (int i = 1; i <= prices.length; i++) {
hold[i] = Math.max(
hold[i-1], // 前一天是已持有状态, 今天继续持有
rest[i-1] - prices[i-1]); // 前一天是冷却期, 今天买进
sold[i] = hold[i-1] + prices[i-1]; // 前一天是持有状态, 今天卖出
rest[i] = Math.max(
rest[i-1], // 前一天是冷却期, 今天依旧不进行任何操作
sold[i-1]); // 前一天是卖出, 今天进入冷却期
}
return Math.max(hold[prices.length],
Math.max(sold[prices.length], rest[prices.length]));
}