Best Time to Buy and Sell Stock with Cooldown

Moderate
0/80
profile
Contributed by
54 upvotes
Asked in companies
AdobeFacebookCiti Bank

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.


Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
4
1 2 3 4


Expected Answer:
3


Output on console:
3


Explanation:
For this test case, prices = [1, 2, 3, 4]. To get the maximum profit you have to buy the stock on day 0 and sell on day 3 to get the maximum profit of 4. Hence the answer is 4.


Sample Input 2:
3
5 4 3


Expected Answer:
0


Output on console:
0


Expected Time Complexity:
Try to solve this in O(n).


Constraints:
1 <= n <= 10^5
1 <= prices[i] <= 10^6

Time Limit: 1 sec
Hint

Try to solve it recursively.

Approaches (3)
Recursive solution

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
Time Complexity

O(2^N), Where N is the size of the array
 

At each recursive step, we are making a choice between two options, there are possibilities of total O(2^N) choices. Hence the final time complexity is O(2^N).

Space Complexity

O(N), Where N is the size of the array
 

The total space complexity of the recursive stack is O(N). Hence the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Best Time to Buy and Sell Stock with Cooldown
Full screen
Console