Skip to content
AI360Xpert
Back to 2-D Dynamic Programming
Medium

Best Time to Buy and Sell Stock with Cooldown

You are given an array `prices` where `prices[i]` is the price of a given stock on the `ith` day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions: - After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day). Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Examples

Input:prices = [1,2,3,0,2]
Output:3
Transactions = [buy, sell, cooldown, buy, sell] Profit = (2 - 1) + (2 - 0) = 3.
Input:prices = [1]
Output:0
We cannot make any profit with only one day.

Constraints

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

State Machine DP

Approach

We can define three states for any given day: 1. `held`: We currently hold a stock. 2. `sold`: We just sold a stock today. 3. `reset`: We are not holding a stock, and we didn't sell one today (cooldown or waiting). For each day, we can transition between these states: - `held` can come from staying in `held` or buying from `reset`. - `sold` can only come from selling from `held`. - `reset` can come from staying in `reset` or transitioning from `sold` (cooldown). We calculate the maximum profit for each state across all days.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(1)

Time complexity is O(n) since we iterate through the prices array exactly once. Space complexity is O(1) as we only use a few variables to track the state on the previous day.

Solution.java
class Solution {    public int maxProfit(int[] prices) {        if (prices == null || prices.length <= 1) return 0;                // Initial states on day 0        int held = -prices[0];        int sold = 0;        int reset = 0;                for (int i = 1; i < prices.length; i++) {            int prevHeld = held;            int prevSold = sold;            int prevReset = reset;                        // State transitions            held = Math.max(prevHeld, prevReset - prices[i]);            sold = prevHeld + prices[i];            reset = Math.max(prevReset, prevSold);        }                return Math.max(sold, reset);    }}