What it teaches: A three-state machine updated daily.
Practise it on judges as “Best Time to Buy and Sell Stock with Cooldown”.
The problem
Unlimited transactions, one share at a time, and after selling you must wait one day before buying again. Return the maximum profit.
Example 1
Input: prices = [1, 2, 3, 0, 2]
Output: 3
Constraints
1 ≤ n ≤ 5000
Pattern clues in the wording
→ Buy/sell with a rule that depends on the previous action
These clues point to 1D Dynamic Programming: Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.
Stuck? Take one hint at a time
Solution.java · starter
class Solution {
public int maxProfit(int[] prices) {
return 0;
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
hold = max(hold, rest − p); sold = hold + p; rest = max(rest, sold), from yesterday's values.
Approach 1
class Solution {
public int maxProfit(int[] prices) {
int hold = Integer.MIN_VALUE / 2, sold = Integer.MIN_VALUE / 2, rest = 0;
for (int p : prices) {
int h = Math.max(hold, rest - p);
int s = hold + p;
int r = Math.max(rest, sold);
hold = h; sold = s; rest = r;
}
return Math.max(sold, rest);
}
}