309. 买卖股票的最佳时机含冷冻期
题目描述
输入一个整数数组 prices，prices[i] 是这支股票第 i 天的价格。
你可以做任意多次买卖，但手里最多同时持有一股：要再次买入，必须先把手上的卖掉。另外，卖出后的第二天是冷冻期，那一天不能买入。
返回能获得的最大利润。
示例 1
输入：prices = [1,2,3,0,2] 输出：3
解释：操作顺序为：第 0 天买入，第 1 天卖出，第 2 天冷冻，第 3 天买入，第 4 天卖出，利润 1 + 2 = 3。
示例 2
输入：prices = [1] 输出：0
解释：只有一天，无法获利。
数据范围
1 <= prices.length <= 50000 <= prices[i] <= 1000
解题思路
每天结束时只有三种状态：hold（持有股票）、sold（当天刚卖出，明天冷冻）、rest（不持有且不在冷冻）。转移：hold 由昨天 hold 保持或昨天 rest 今天买入；sold 只能由昨天 hold 今天卖出；rest 由昨天 rest 或 sold（冷冻结束）而来。买入只能从 rest 发生，这就实现了冷冻期。
为什么正确
处理完第 i 天后，hold/sold/rest 分别是第 i 天结束处于该状态时的最大利润。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
三个新状态要用昨天的旧值同时计算，不能边算边覆盖；买入必须用 rest - p 而不是 sold - p。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
hold, sold, rest = -prices[0], 0, 0
for p in prices[1:]:
nh = max(hold, rest - p)
ns = hold + p
nr = max(rest, sold)
hold, sold, rest = nh, ns, nr
return max(sold, rest)class Solution {
public int maxProfit(int[] prices) {
int hold = -prices[0], sold = 0, rest = 0;
for (int i = 1; i < prices.length; i++) {
int p = prices[i];
int nh = Math.max(hold, rest - p);
int ns = hold + p;
int nr = Math.max(rest, sold);
hold = nh; sold = ns; rest = nr;
}
return Math.max(sold, rest);
}
}class Solution {
public:
int maxProfit(vector<int>& prices) {
int hold = -prices[0], sold = 0, rest = 0;
for (size_t i = 1; i < prices.size(); i++) {
int p = prices[i];
int nh = max(hold, rest - p);
int ns = hold + p;
int nr = max(rest, sold);
hold = nh; sold = ns; rest = nr;
}
return max(sold, rest);
}
};func maxProfit(prices []int) int {
hold, sold, rest := -prices[0], 0, 0
for _, p := range prices[1:] {
nh := max(hold, rest-p)
ns := hold + p
nr := max(rest, sold)
hold, sold, rest = nh, ns, nr
}
return max(sold, rest)
}var maxProfit = function(prices) {
let hold = -prices[0], sold = 0, rest = 0;
for (const p of prices.slice(1)) {
const nh = Math.max(hold, rest - p);
const ns = hold + p;
const nr = Math.max(rest, sold);
[hold, sold, rest] = [nh, ns, nr];
}
return Math.max(sold, rest);
};function maxProfit(prices: number[]): number {
let hold = -prices[0], sold = 0, rest = 0;
for (const p of prices.slice(1)) {
const nh = Math.max(hold, rest - p);
const ns = hold + p;
const nr = Math.max(rest, sold);
[hold, sold, rest] = [nh, ns, nr];
}
return Math.max(sold, rest);
}