LeetCode 309: Best Time to Buy and Sell Stock with Cooldown (State DP: Hold / Sold / Rest)
LeetCode 309Dynamic ProgrammingState MachineToday we solve LeetCode 309 - Best Time to Buy and Sell Stock with Cooldown.
Source: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
English
Problem Summary
You may complete as many buy/sell transactions as you want, but after selling stock, you must wait one day before buying again. Return the maximum profit.
Key Insight
Each day can be represented by three states: hold (currently holding stock), sold (just sold today), and rest (not holding and not selling today). Cooldown is naturally enforced by allowing buy only from yesterday's rest.
State Transitions
newHold = max(oldHold, oldRest - price)
newSold = oldHold + price
newRest = max(oldRest, oldSold)
Answer is max(sold, rest) on the last day, because ending with a hold means unsold stock.
Complexity Analysis
Let n be number of days.
Time: O(n).
Space: O(1).
Common Pitfalls
- Buying from sold directly, which breaks cooldown.
- Returning max(hold, sold, rest) (hold should not be final answer).
- Overwriting states in wrong order without temporary variables.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int hold = -prices[0];
int sold = 0;
int rest = 0;
for (int i = 1; i < prices.length; i++) {
int prevHold = hold;
int prevSold = sold;
int prevRest = rest;
hold = Math.max(prevHold, prevRest - prices[i]);
sold = prevHold + prices[i];
rest = Math.max(prevRest, prevSold);
}
return Math.max(sold, rest);
}
}func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
hold := -prices[0]
sold := 0
rest := 0
for i := 1; i < len(prices); i++ {
prevHold, prevSold, prevRest := hold, sold, rest
if prevRest-prices[i] > prevHold {
hold = prevRest - prices[i]
} else {
hold = prevHold
}
sold = prevHold + prices[i]
if prevRest > prevSold {
rest = prevRest
} else {
rest = prevSold
}
}
if sold > rest {
return sold
}
return rest
}class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) return 0;
int hold = -prices[0], sold = 0, rest = 0;
for (int i = 1; i < (int)prices.size(); i++) {
int prevHold = hold, prevSold = sold, prevRest = rest;
hold = max(prevHold, prevRest - prices[i]);
sold = prevHold + prices[i];
rest = max(prevRest, prevSold);
}
return max(sold, rest);
}
};class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
hold = -prices[0]
sold = 0
rest = 0
for price in prices[1:]:
prev_hold, prev_sold, prev_rest = hold, sold, rest
hold = max(prev_hold, prev_rest - price)
sold = prev_hold + price
rest = max(prev_rest, prev_sold)
return max(sold, rest)var maxProfit = function(prices) {
if (prices.length === 0) return 0;
let hold = -prices[0];
let sold = 0;
let rest = 0;
for (let i = 1; i < prices.length; i++) {
const prevHold = hold;
const prevSold = sold;
const prevRest = rest;
hold = Math.max(prevHold, prevRest - prices[i]);
sold = prevHold + prices[i];
rest = Math.max(prevRest, prevSold);
}
return Math.max(sold, rest);
};中文
题目概述
你可以进行任意次买卖，但卖出股票后必须冷冻 1 天（下一天不能买入）。求最大利润。
核心思路
每天只有三种状态：hold（手里有股票）、sold（当天刚卖出）、rest（当天休息且手里无股票）。
冷冻期约束通过转移自然体现：买入只能从前一天的 rest 转来，不能从 sold 直接买。
状态转移
newHold = max(oldHold, oldRest - price)
newSold = oldHold + price
newRest = max(oldRest, oldSold)
最终答案是最后一天的 max(sold, rest)，因为以 hold 结尾代表股票还没卖出。
复杂度分析
设天数为 n。
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 把买入写成从 sold 转移，破坏冷冻期。
- 最终返回 max(hold, sold, rest)（hold 不应计入答案）。
- 原地更新状态时没有先缓存旧值，导致转移污染。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int hold = -prices[0];
int sold = 0;
int rest = 0;
for (int i = 1; i < prices.length; i++) {
int prevHold = hold;
int prevSold = sold;
int prevRest = rest;
hold = Math.max(prevHold, prevRest - prices[i]);
sold = prevHold + prices[i];
rest = Math.max(prevRest, prevSold);
}
return Math.max(sold, rest);
}
}func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
hold := -prices[0]
sold := 0
rest := 0
for i := 1; i < len(prices); i++ {
prevHold, prevSold, prevRest := hold, sold, rest
if prevRest-prices[i] > prevHold {
hold = prevRest - prices[i]
} else {
hold = prevHold
}
sold = prevHold + prices[i]
if prevRest > prevSold {
rest = prevRest
} else {
rest = prevSold
}
}
if sold > rest {
return sold
}
return rest
}class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) return 0;
int hold = -prices[0], sold = 0, rest = 0;
for (int i = 1; i < (int)prices.size(); i++) {
int prevHold = hold, prevSold = sold, prevRest = rest;
hold = max(prevHold, prevRest - prices[i]);
sold = prevHold + prices[i];
rest = max(prevRest, prevSold);
}
return max(sold, rest);
}
};class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
hold = -prices[0]
sold = 0
rest = 0
for price in prices[1:]:
prev_hold, prev_sold, prev_rest = hold, sold, rest
hold = max(prev_hold, prev_rest - price)
sold = prev_hold + price
rest = max(prev_rest, prev_sold)
return max(sold, rest)var maxProfit = function(prices) {
if (prices.length === 0) return 0;
let hold = -prices[0];
let sold = 0;
let rest = 0;
for (let i = 1; i < prices.length; i++) {
const prevHold = hold;
const prevSold = sold;
const prevRest = rest;
hold = Math.max(prevHold, prevRest - prices[i]);
sold = prevHold + prices[i];
rest = Math.max(prevRest, prevSold);
}
return Math.max(sold, rest);
};
Comments