Best Time to Buy and Sell Stock with Cooldown

Medium
309.

Best Time to Buy and Sell Stock with Cooldown

Best Time to Buy and Sell Stock with Cooldown is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and Bloomberg interviews.

You are given an array prices where prices[i] is the price of a stock on day i.

You may complete as many transactions as you like — buy one share and later sell it — with two restrictions: you may hold at most one share at a time, and after you sell you must wait one full day before buying again (a cooldown).

Return the maximum profit.

Example 1

Input
prices = [1,2,3,0,2]
Output
3
Explanation
buy, sell, cooldown, buy, sell.

Example 2

Input
prices = [1]
Output
0

Example 3

Input
prices = [2,1]
Output
0

Constraints

  • 1 <= prices.length <= 40
  • 0 <= prices[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Best Time to Buy and Sell Stock with Cooldown — Solution

Best Time to Buy and Sell Stock with Cooldown solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Best Time to Buy and Sell Stock with Cooldown is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and Bloomberg interviews.

Problem statement

You are given an array prices where prices[i] is the price of a stock on day i.

You may complete as many transactions as you like — buy one share and later sell it — with two restrictions: you may hold at most one share at a time, and after you sell you must wait one full day before buying again (a cooldown).

Return the maximum profit.

Example 1

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: buy, sell, cooldown, buy, sell.

Example 2

Input: prices = [1]
Output: 0

Example 3

Input: prices = [2,1]
Output: 0

Constraints

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

Hints for Best Time to Buy and Sell Stock with Cooldown

  1. Hint 1

    Each day you are in exactly one of three states: holding a share, having just sold, or resting with nothing.

  2. Hint 2

    hold can come from staying held or from buying while resting; sold only ever comes from selling what you held.

  3. Hint 3

    rest absorbs the cooldown — it takes the previous day's sold, which is what forbids buying the day after a sale.

How to solve Best Time to Buy and Sell Stock with Cooldown

Three states per day — hold (own a share), sold (sold today), rest (own nothing, free to buy) — with the cooldown enforced by feeding rest from the previous day's sold.

Approach

  1. Initialise hold = -∞, sold = 0, rest = 0.
  2. For each price: sold = hold + price; hold = max(hold, rest - price); rest = max(rest, prevSold).
  3. Return max(sold, rest).

Why it works

Every day the trader is in exactly one state, and each transition is the best of its legal predecessors. Buying is only allowed from rest, and rest only absorbs sold one day later, which is precisely the one-day cooldown.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Save the previous sold before overwriting it, or the cooldown silently disappears.
  • The answer is never hold — ending with an unsold share is dominated.

Reference solution

Python

def maxProfit(prices) -> int:
    hold = float("-inf")
    sold = 0
    rest = 0
    for price in prices:
        prev_sold = sold
        sold = hold + price
        hold = max(hold, rest - price)
        rest = max(rest, prev_sold)
    return max(sold, rest)

Java

public static int maxProfit(int[] prices) {
    final int NEG = -1000000;
    int hold = NEG, sold = 0, rest = 0;
    for (int price : prices) {
        int prevSold = sold;
        sold = hold + price;
        hold = Math.max(hold, rest - price);
        rest = Math.max(rest, prevSold);
    }
    return Math.max(sold, rest);
}

C++

int maxProfit(vector<int>& prices) {
    const int NEG = -1000000;
    int hold = NEG, sold = 0, rest = 0;
    for (int price : prices) {
        int prevSold = sold;
        sold = hold + price;
        hold = max(hold, rest - price);
        rest = max(rest, prevSold);
    }
    return max(sold, rest);
}

JavaScript

var maxProfit = function(prices) {
    let hold = -Infinity, sold = 0, rest = 0;
    for (let i = 0; i < prices.length; i++) {
        const prevSold = sold;
        sold = hold + prices[i];
        hold = Math.max(hold, rest - prices[i]);
        rest = Math.max(rest, prevSold);
    }
    return Math.max(sold, rest);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming