Best Time to Buy and Sell Stock with Cooldown

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).

Example 1:

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

Example 2:

Input: prices = [1]
Output: 0

Constraints:

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

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

public int maxProfit(int[] prices) {
    int n = prices.length;

    if(n < 2) return 0;

    int prevSell = 0, sell = 0, buy = Integer.MIN_VALUE;

    for(int price: prices){
        int newBuy = Math.max(buy, prevSell - price);
        int newSell = Math.max(sell, buy + price);

        prevSell = sell;
        buy = newBuy;
        sell = newSell;
    }

    return sell;
}

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let n = prices.length;

  if (n < 2) return 0;

  let prevSell = 0,
    sell = 0,
    buy = -Infinity;

  for (let price of prices) {
    let newBuy = Math.max(buy, prevSell - price);
    let newSell = Math.max(sell, buy + price);

    prevSell = sell;
    buy = newBuy;
    sell = newSell;
  }

  return sell;
};

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)

        if n < 2:
            return 0

        prevSell = 0
        sell = 0
        buy = float('-inf')

        for price in prices:
            newBuy = max(buy, prevSell - price)
            newSell = max(sell, buy + price)

            prevSell = sell
            buy = newBuy
            sell = newSell

        return sell

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        if (n < 2) return 0;

        int prevSell = 0, sell = 0, buy = std::numeric_limits<int>::min();

        for (int price : prices) {
            int newBuy = std::max(buy, prevSell - price);
            int newSell = std::max(sell, buy + price);

            prevSell = sell;
            buy = newBuy;
            sell = newSell;
        }

        return sell;
    }
};

Time/Space Complexity:

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

Explanation:

So, there are two rules we have to follow as per problem statement:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

If we represent buying and selling with two arrays buy and sell, where buy[i] means maximum profit for day i when we consider buying, and sell[i] maximum profit for day i when we can consider selling, we can form two recurrence relations:

buy[i] = Math.max(buy[i-1], sell[i-2] - price)
sell[i] = Math.max(sell[i-1], buy[i-1] + price);

So, for each day i for buying we can optimize max profit by taking the maximum from the previous buy day i-1 and do nothing, or we can take i-2 selling day (i-2, since on i-1 we would have cooldown) and buy the stock at the day i. For each day i we can optimize selling by either having sold yesterday i-1 and do nothing today (cooldown), or sell today but only if have already bought yesterday buy[i-1]. Our base cases will be all 0 except for buy[1] which we put to minimum value in order to trigger the calculation in the loop. Note that values are shifted by 2 so we that we don't run into out of boundary errors.

Java
JavaScript
Python
C++

public int maxProfit(int[] prices) {
    int n = prices.length;
    int[] buy = new int[n+2], sell = new int[n+2];
    buy[1] = Integer.MIN_VALUE;

    for(int i = 2; i < n + 2; ++i){
        buy[i] = Math.max(buy[i-1], sell[i-2] - prices[i-2]);
        sell[i] = Math.max(sell[i-1], buy[i-1] + prices[i-2]);
    }

    return sell[n+1];
}

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let n = prices.length;
  let buy = new Array(n + 2);
  let sell = new Array(n + 2);
  buy[1] = Number.MIN_SAFE_INTEGER;

  for (let i = 2; i < n + 2; i++) {
    buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i - 2]);
    sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i - 2]);
  }

  return sell[n + 1];
};

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
      n = len(prices)
      buy = [0] * (n + 2)
      sell = [0] * (n + 2)
      buy[1] = float('-inf')

      for i in range(2, n + 2):
          buy[i] = max(buy[i - 1], sell[i - 2] - prices[i - 2])
          sell[i] = max(sell[i - 1], buy[i - 1] + prices[i - 2])

      return sell[n + 1]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        std::vector<int> buy(n + 2, std::numeric_limits<int>::min());
        std::vector<int> sell(n + 2);

        for (int i = 2; i < n + 2; i++) {
            buy[i] = std::max(buy[i - 1], sell[i - 2] - prices[i - 2]);
            sell[i] = std::max(sell[i - 1], buy[i - 1] + prices[i - 2]);
        }

        return sell[n + 1];
    }
};

If you take a closer look you will notice that we don't need whole arrays, but only at most two previous values (e.g. sell[i-2]), so we can optimize further to constant space complexity as shown in the final implementation in the Solution section.

Example 1:​

Example 2:​

Constraints:​

Solution:​

Time/Space Complexity:​