101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. State Machine Approach - Complex approach
  2. Dynamic Programming Approach - Complex approach
  3. Optimized Dynamic Programming Approach - Complex approach

Approach 1: State Machine Approach

The key insight for solving this problem is to use a state machine approach to model the different states we can be in on each day, and the transitions between these states.

Let's define three states:

  • hold: The maximum profit we can have if we are holding a stock at the end of day i.
  • sold: The maximum profit we can have if we have just sold a stock at the end of day i.
  • rest: The maximum profit we can have if we are not holding a stock and not in a cooldown period at the end of day i.

For each day, we have the following state transitions:

  • hold = max(hold, rest - prices[i]): We either continue holding the stock from the previous day, or we buy a new stock using our rest state profit.
  • sold = hold + prices[i]: If we sell the stock we're holding, we get the profit from the hold state plus the current price.
  • rest = max(rest, sold): We either continue resting, or we come from the sold state (which means we've completed the cooldown period).

At the end, the maximum profit will be the maximum of the sold and rest states, as we don't want to end up holding a stock.

Algorithm:

  1. Initialize hold = -prices[0] (maximum profit with a stock), sold = 0 (maximum profit after selling), and rest = 0 (maximum profit at rest).
  2. Iterate through the prices array starting from the second day (i = 1):
  3. a. Calculate the new hold value: hold = max(hold, rest - prices[i]).
  4. b. Calculate the new sold value: sold = hold + prices[i].
  5. c. Calculate the new rest value: rest = max(rest, sold).
  6. d. Update the hold value with the new hold value.
  7. Return max(sold, rest) as the maximum profit.

Time Complexity:

O(n)

Where n is the length of the prices array. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Approach 2: Dynamic Programming Approach

Another way to think about this problem is to use dynamic programming to track the maximum profit at each day for different states.

Let's define three arrays:

  • buy[i]: The maximum profit we can have if we buy a stock at the end of day i.
  • sell[i]: The maximum profit we can have if we sell a stock at the end of day i.
  • cooldown[i]: The maximum profit we can have if we are in the cooldown state at the end of day i.

For each day, we have the following state transitions:

  • buy[i] = max(buy[i-1], cooldown[i-1] - prices[i]): We either continue from the previous buy state, or we buy a new stock after cooldown.
  • sell[i] = max(sell[i-1], buy[i-1] + prices[i]): We either continue from the previous sell state, or we sell the stock we bought previously.
  • cooldown[i] = max(cooldown[i-1], sell[i-1]): We either continue from the previous cooldown state, or we enter cooldown after selling.

At the end, the maximum profit will be the maximum of the sell[n-1] and cooldown[n-1] states.

Algorithm:

  1. Initialize arrays buy, sell, and cooldown of size n.
  2. Set buy[0] = -prices[0], sell[0] = 0, and cooldown[0] = 0.
  3. Iterate through the prices array starting from the second day (i = 1):
  4. a. Calculate buy[i] = max(buy[i-1], cooldown[i-1] - prices[i]).
  5. b. Calculate sell[i] = max(sell[i-1], buy[i-1] + prices[i]).
  6. c. Calculate cooldown[i] = max(cooldown[i-1], sell[i-1]).
  7. Return max(sell[n-1], cooldown[n-1]) as the maximum profit.

Time Complexity:

O(n)

Where n is the length of the prices array. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(n)

We use three arrays of size n to store the maximum profit for each state at each day.

Approach 3: Optimized Dynamic Programming Approach

We can optimize the dynamic programming approach by using only a constant amount of extra space.

Since we only need the values from the previous day to calculate the values for the current day, we can use variables instead of arrays to track the maximum profit for each state.

This approach is essentially the same as the state machine approach, but it provides a different mental model for understanding the problem.

Algorithm:

  1. Initialize variables buy = -prices[0], sell = 0, and cooldown = 0.
  2. Iterate through the prices array starting from the second day (i = 1):
  3. a. Calculate the new buy value: newBuy = max(buy, cooldown - prices[i]).
  4. b. Calculate the new sell value: newSell = max(sell, buy + prices[i]).
  5. c. Calculate the new cooldown value: newCooldown = max(cooldown, sell).
  6. d. Update buy = newBuy, sell = newSell, and cooldown = newCooldown.
  7. Return max(sell, cooldown) as the maximum profit.

Time Complexity:

O(n)

Where n is the length of the prices array. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function maxProfit(prices):
    n = length of prices
    if n <= 1:
        return 0
 
    hold = -prices[0]  // Maximum profit with a stock
    sold = 0  // Maximum profit after selling
    rest = 0  // Maximum profit at rest
 
    for i from 1 to n-1:
        prevHold = hold
        hold = max(hold, rest - prices[i])  // Continue holding or buy
        sold = prevHold + prices[i]  // Sell the stock
        rest = max(rest, sold)  // Continue resting or come from sold
 
    return max(sold, rest)
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone