Best Time to Buy and Sell Stock with Cooldown

Medium

Problem

You may make as many transactions as you like, holding at most one share at a time. After selling, you cannot buy on the next day (a one-day cooldown). Return the maximum profit.

Example 1

Input:  [1, 2, 3, 0, 2]
Output: 3

Buy, sell, cooldown, buy, sell.

Test cases

Case 1

Input:    [1,2,3,0,2]
Expected: 3

Case 2

Input:    [1]
Expected: 0

Case 3

Input:    [1,2,4]
Expected: 3

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. State machine: hold / sold / rest

Time O(n)Space O(1)

hold = max(hold, rest − price); sold = hold + price; rest = max(rest, sold of yesterday). Buying needs yesterday to be rest, which enforces the cooldown.

function maxProfit(prices) {
let hold = -Infinity, sold = 0, rest = 0;
for (const p of prices) {
const prevSold = sold;
sold = hold + p;
hold = Math.max(hold, rest - p);
rest = Math.max(rest, prevSold);
}
return Math.max(sold, rest);
}