algoadvance

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

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restriction: After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2:

Input: prices = [1]
Output: 0

Clarifying Questions

  1. How are the transactions represented in the output?
    • The output should only show the total maximum profit.
  2. Can the input prices array be empty?
    • Yes. If the prices array is empty, the output should be 0.
  3. Are there any constraints on the size of the prices array?
    • No specific constraints, but performance should be considered for large inputs.

Strategy

To tackle this problem, we can use Dynamic Programming (DP). We’ll maintain three states:

  1. hold: The maximum profit we can have if we currently hold a stock.
  2. sold: The maximum profit we can have if we have just sold a stock (i.e., cooldown starts next day).
  3. rest: The maximum profit we can have if we are in a cooldown period or have done nothing today.

We will update these states iteratively as we go through each price in the array.

State Transition

  1. hold[i]: We can either continue holding the stock (hold[i-1]), or we can buy the stock today (so we should be at a rest state the previous day, rest[i-1] - prices[i]).
  2. sold[i]: We can only sell if we were holding the stock the previous day (hold[i-1] + prices[i]).
  3. rest[i]: We could be in rest from being in rest (rest[i-1]) or from just selling the stock (sold[i-1]).

The answer will be the maximum value between sold and rest on the last day because we can either be resting or have just sold the stock for maximum profit.

Code

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        n = len(prices)
        
        hold = [0]*n
        sold = [0]*n
        rest = [0]*n
        
        hold[0] = -prices[0]
        sold[0] = 0
        rest[0] = 0
        
        for i in range(1, n):
            hold[i] = max(hold[i-1], rest[i-1] - prices[i])
            sold[i] = hold[i-1] + prices[i]
            rest[i] = max(rest[i-1], sold[i-1])
        
        return max(sold[n-1], rest[n-1])

# Example Usage
sol = Solution()
prices = [1, 2, 3, 0, 2]
print(sol.maxProfit(prices))  # Output: 3

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the length of the prices array since we iterate through the array only once. The space complexity is also (O(n)) due to the storage of the hold, sold, and rest arrays for each day.

Try our interview co-pilot at AlgoAdvance.com