Best Time To Buy And Sell Stock With Cooldown - Leetcode Solution

The Best Time to Buy and Sell Stock with Cooldown problem on LeetCode is a dynamic programming problem where the goal is to maximize the profit of a given stock with a one-day cooldown period.

Problem statement:

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

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day to sell that stock.

You are also given a cooldown period of one day, i.e., no transactions can be made on the next day after a sell.

Return the maximum profit you can achieve.

Solution:

To solve this problem, we can use dynamic programming to keep track of the maximum profit we can make on each day.

We will create two arrays:

1. buy[i] - the maximum profit we can make by buying the stock on day i
2. sell[i] - the maximum profit we can make by selling the stock on day i

We can compute the buy and sell arrays using the following recurrence relation:

buy[i] = max(sell[i-2] - prices[i], buy[i-1]) sell[i] = max(buy[i-1] + prices[i], sell[i-1])

The buy array keeps track of the maximum profit we can make by buying the stock on day i.

To compute buy[i], we have two options:

1. Not buy the stock on day i and carry forward the maximum profit from the previous day, buy[i-1].
2. Buy the stock on day i by subtracting the price of the stock on day i, prices[i], from the maximum profit we can make by selling the stock on day i-2, sell[i-2].

The sell array keeps track of the maximum profit we can make by selling the stock on day i.

To compute sell[i], we have two options:

1. Not sell the stock on day i and carry forward the maximum profit from the previous day, sell[i-1].
2. Sell the stock on day i by adding the price of the stock on day i, prices[i], to the maximum profit we can make by buying the stock on day i-1, buy[i-1].

We will return sell[n-1], where n is the length of the prices array, as it will give us the maximum profit we can make by selling the stock on the last day.

Code:

Here is the Python code to solve this problem:

def maxProfit(prices: List[int]) -> int: n = len(prices) if n < 2: return 0 buy = [0] * n sell = [0] * n buy[0] = -prices[0] for i in range(1, n): buy[i] = max(sell[i-2] - prices[i], buy[i-1]) sell[i] = max(buy[i-1] + prices[i], sell[i-1]) return sell[n-1]

Time complexity:

The time complexity of this solution is O(n), where n is the length of the prices array, as we only need to loop through the array once to calculate the buy and sell arrays.

Space complexity:

The space complexity of this solution is O(n), as we are storing two arrays buy and sell of length n.

1