动态规划中等1 种解法
#309买卖股票的最佳时机含冷冻期
交易次数不限，但卖出后的下一天不能买入，求最大利润。
#数组#动态规划#状态机#股票
原题
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1] 输出: 0
提示：
1 <= prices.length <= 50000 <= prices[i] <= 1000
解题主线
- 每天结束时严格区分休息、持股、当天卖出三种状态；只有前一天处于休息状态，今天才能买入。
- 今天的休息状态可来自昨天继续休息或昨天卖出，后者经过今天后才解除冷冻。
- 当天卖出必须来自昨天持股，不能从今天刚买入的状态转移。
解法 1：三状态动态规划
维护 rest（不持股且今天未卖出）、hold（持股）和 sold（今天卖出）；买入只能从前一天 rest 转移，从而自然落实一天冷冻期。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
final class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int rest = 0;
int hold = -prices[0];
// 首日不可能卖出，用负无穷表示该状态不可达。
int sold = Integer.MIN_VALUE;
for (int i = 1; i < prices.length; i++) {
// 保存前一天快照，避免同一天的新状态串联转移。
int previousRest = rest;
int previousHold = hold;
int previousSold = sold;
// 休息可来自继续休息或昨天卖出后度过冷冻日。
rest = Math.max(previousRest, previousSold);
// 买入只能来自昨天的 rest，不能紧接在卖出后的次日。
hold = Math.max(previousHold, previousRest - prices[i]);
sold = previousHold + prices[i];
}
// 最终持股尚未兑现利润，只比较两个不持股状态。
return Math.max(rest, sold);
}
}实现提示
- Integer.MIN_VALUE 只用于首日不可达的 sold；后续 sold 始终由可达的 hold 加价格得到，不会发生哨兵加法溢出。
边界与易错点
- 旧 Q188_maxStockProfit_frozen 实际属于题号 309，且状态注释与转移方程错位；例如 [2, 1] 会错误返回 1，不能直接保留。
- 休息状态不是“当天处于冷冻期”的同义词：它表示今天没有卖出且不持股，下一天允许买入。
- 当天卖出状态在第 0 天不可达，应使用负无穷哨兵而不是 0，避免状态语义被放宽。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/greedy/Q188_maxStockProfit_frozen.javaleetcode/src/main/java/greedy/Q309_maxStockProfit_frozen.java