Stock Buy and Sell with Cooldown

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

DP: after selling, must wait one day. States: held (own stock), sold (just sold today), rest (cooldown passed).

Algorithm

1held = -infinity, sold = 0, rest = 0.
2For each price: new_held = max(held, rest - price). new_sold = held + price. new_rest = max(rest, sold).
3Return max(sold, rest) at end.

Common Pitfalls

•After selling (sold state), next day must be rest (cannot buy). After rest, can buy or rest.

Stock Buy and Sell with Cooldown.java

Java

// Approach: DP with three states: hold, sold (cooldown), rest. Transition between states each day.
// Time: O(n) Space: O(1)
class Solution {
    public int maxProfit(int arr[]) {
        int n = arr.length;
        if (n == 0)
            return 0;

        long dp0 = 0;
        long dp1 = -arr[0];
        long dp2 = 0;

        for (int i = 1; i < n; ++i) {
            long price = arr[i];
            long prev0 = dp0, prev1 = dp1, prev2 = dp2;

            dp0 = Math.max(prev0, prev2);
            dp1 = Math.max(prev1, prev0 - price);
            dp2 = prev1 + price;
        }

        return (int) Math.max(dp0, dp2);
    }
}

Was this solution helpful?