Best Time to Buy and Sell Stock with Cooldown

Moderate

0/80

Contributed by

49 upvotes

Asked in companies

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:

Output on console:

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:

Output on console:

Expected Time Complexity:

Try to solve this in O(n).

Constraints:

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

Time Limit: 1 sec

Console