Last Updated: 21 Nov, 2021

Best Time to Buy and Sell Stock with Cooldown

Moderate

Asked in companies

Solve now

Problem statement

You are given a list of stock prices of size 'n' called ‘prices’, where ‘prices[i]’ represents the price on ‘i’th day.

Your task is to calculate the maximum profit you can earn by trading stocks if you can only hold one stock at a time.

After you sell your stock on the ‘i’th day, you can only buy another stock on ‘i + 2’ th day or later.

Example:

Input: 'prices' = [4, 9, 0, 4, 10]

Output: 11

Explanation:
You are given prices = [4, 9, 0, 4, 10]. To get maximum profits you will have to buy on day 0 and sell on day 1 to make a profit of 5, and then you have to buy on day 3  and sell on day 4 to make the total profit of 11. Hence the maximum profit is 11.

Input Format:

The first line of input contains a single integer ‘n’ representing the length of the ‘prices’ array.

The second line of input contains ‘n’ space-separated integers representing the elements of the array ‘prices’.

Output Format:

Return the maximum possible profit you can get from the stocks.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

In this approach, at each day we are either holding a stock or not. If on any given day we are holding stock, we have two choices to sell it at the current price or hold it further, otherwise, if we are not holding the stock we still have two choices, to buy at the current price or not buy. If we do not buy/ sell stock we just move to the next day with the same state, if we sell the stock on a given day we have to move to the day after the next day.

We will create a recursive function getMaxProfit(prices, currentDay, holding), where prices are the array of prices of stocks, currentDay, is the stock day on which we are checking to sell or buy stock, and holding a boolean variable that is true if we are holding a stock currently.

Algorithm:

In the function getMaxProfit(prices, currDay, holding):
- If currDay is greater than or equal to size of prices
  - Return 0
- Set currMaxProfit as 0
- If holding is true
  - Set sellProfit as getMaxProfit(prices, currDay + 2, False) + prices[currDay]
  - Set noSellProfit as getMaxProfit(prices, currDay + 1, True)
  - Set currMaxProfit as maximum of sellProfit and noSellProfit
- Otherwise,
  - Set buyProfit as getMaxProfit(prices, currDay + 1, True) - prices[i]
  - Set noBuyProfit as getMaxProfit(prices, currDay + 1, False)
  - Set currMaxProfit as maximum of buyProft and noBuyProfit
- Return currMaxProfit

Solve now

02 Approach

In this approach, we will use the same method as the last approach, but we make a cache, which stores the maximum profit for each day, whether we are holding the stock or not holding the stock on that day.

Therefore we will have to create two arrays or a 2D matrix of two rows, to store values of each day where, cache[0][i] and cache[1][i], represents the maximum possible profit of ith day we are not holding the stock and holding the stock respectively on the ‘i’th day.

Algorithm:

In the function getMaxProfit(prices, currDay, holding, cache):
- If currDay is greater than or equal to size of prices
  - Return 0
- if cache[holding][currDay] does not equal to -1, return it.
- Set currMaxProfit as 0
- If holding is true
  - Set sellProfit as getMaxProfit(prices, currDay + 2, False, cache) + prices[currDay]
  - Set noSellProfit as getMaxProfit(prices, currDay + 1, True, cache)
  - Set currMaxProfit as maximum of sellProfit and noSellProfit
- Otherwise,
  - Set buyProfit as getMaxProfit(prices, currDay + 1, True, cache) - prices[i]
  - Set noBuyProfit as getMaxProfit(prices, currDay + 1, False, cache)
  - Set currMaxProfit as maximum of buyProft and noBuyProfit
- Set cache[holding][currDay] as currMaxProfit
- Return currMaxProfit

Solve now

03 Approach

In this approach, we try to use the previous day’s solutions to figure out the solution of the current day. On any given day we will have to calculate two different values, the maximum profit when we are holding a share and not holding any share on the current day.

We will create a 2D array of 2 rows, profits, to store values of each day where, profit[0][i] and profits[1][i], represents the maximum possible profit of ith day we are not holding the stock and holding the stock respectively on the ‘i’th day.

Algorithm:

Initialise a 2D array profits with 2 rows with size equal to prices array
Set profits[0][0] as 0 and profits[1][0] as -prices[0]
Set profits[0][1] as maximum of profits[0][0] and profits[1][0] + prices[1]
Set profits[1][1] as maximum of profits[1][0] and profits[0][0] - prices[1]
Iterate currDay from 2 to size of prices array
- Set profits[0][currDay] as maximum of profits[0][currDay - 1] and profits[1][currDay] + prices[currDay]
- Set profits[1][currDay] as maximum profits[1][currDay - 1] and profits[0][currDay - 2] - prices[currDay]
Return the maximum of last elements of profits[0] and profits[1]

Solve now