Best Time to Buy and Sell Stock with Cooldown

Problem Statement

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

You may buy and sell one PythonCoin multiple times with the following restrictions:

  • After you sell your PythonCoin, you cannot buy another one on the next day (i.e., there is a cooldown period of one day).
  • You may only own at most one PythonCoin at a time.

You may complete as many transactions as you like.

Return the maximum profit you can achieve.

Example 1:

Input: prices = [1,3,4,0,4]


Output: 6

Explanation: Buy on day 0 (price = 1) and sell on day 1 (price = 3), profit = 3-1 = 2. Then buy on day 3 (price = 0) and sell on day 4 (price = 4), profit = 4-0 = 4. Total profit is 2 + 4 = 6.

Example 2:

Input: prices = [1]


Output: 0

Constraints:

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

You should aim for a solution with O(n) time and O(1) space, where n is the length of the prices array.

Hint 1

Consider using dynamic programming to solve this problem. You can define states based on whether you are buying or selling and the current day.

Hint 2

Think about the cooldown period. How does it affect the transitions between states in your dynamic programming solution?

Hint 3

Can you optimize the space complexity of your dynamic programming solution by only keeping track of the necessary previous states?

Solution

Recursion

def max_profit(prices: List[int]) -> int:
    def dfs(i: int, buying: bool) -> int:
        if i >= len(prices):
            return 0


        cooldown = dfs(i + 1, buying)
        if buying:
            buy = dfs(i + 1, not buying) - prices[i]
            return max(buy, cooldown)
        else:
            sell = dfs(i + 2, not buying) + prices[i]
            return max(sell, cooldown)


    return dfs(0, True)

Time complexity: O(2 ^ n) Space complexity: O(n)