hardDynamic Programming 1DPure DSA~35 min
Maximum Profit With a One-Day Cooldown
You may buy and sell a single asset repeatedly, but after each sale you must sit out one day before buying again. Maximize total profit over a price series.
Problem
Given an array prices where prices[i] is the price on day i, return the maximum profit. You may complete as many transactions as you like (buy then sell), but you cannot buy on the day immediately after a sell, and you cannot hold more than one unit at a time.
Input
An integer array prices.
Output
An integer: the maximum achievable profit.
Constraints
- 1 <= prices.length <= 5000
- 0 <= prices[i] <= 1000
- One unit held at a time.
Examples
Example 1
Input
prices = [1,2,3,0,2]
Output
3
buy 1, sell 3 (profit 2), cooldown, buy 0, sell 2 (profit 1) -> 3.
Example 2
Input
prices = [1]
Output
0
No transaction is possible.