101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming with Four States - Complex approach
  2. Dynamic Programming with Arrays - Complex approach
  3. Split and Conquer Approach - Complex approach

Approach 1: Dynamic Programming with Four States

The key insight for solving this problem is to use dynamic programming to track the maximum profit after different states of transactions.

Let's define four variables to represent the maximum profit at different states:

  • buy1: Maximum profit after buying the first stock.
  • sell1: Maximum profit after selling the first stock.
  • buy2: Maximum profit after buying the second stock.
  • sell2: Maximum profit after selling the second stock.

For each day, we have the following state transitions:

  • buy1 = max(buy1, -prices[i]): Either keep the previous state or buy the first stock.
  • sell1 = max(sell1, buy1 + prices[i]): Either keep the previous state or sell the first stock.
  • buy2 = max(buy2, sell1 - prices[i]): Either keep the previous state or buy the second stock using the profit from the first transaction.
  • sell2 = max(sell2, buy2 + prices[i]): Either keep the previous state or sell the second stock.

At the end, sell2 will represent the maximum profit after at most two transactions.

Algorithm:

  1. Initialize buy1 = -prices[0], sell1 = 0, buy2 = -prices[0], and sell2 = 0.
  2. Iterate through the prices array starting from the second day (i = 1):
  3. a. Update buy1 = max(buy1, -prices[i]).
  4. b. Update sell1 = max(sell1, buy1 + prices[i]).
  5. c. Update buy2 = max(buy2, sell1 - prices[i]).
  6. d. Update sell2 = max(sell2, buy2 + prices[i]).
  7. Return sell2 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 with Arrays

Another approach is to use dynamic programming with arrays to track the maximum profit at each day for different states.

Let's define four arrays:

  • buy1[i]: Maximum profit after buying the first stock on day i.
  • sell1[i]: Maximum profit after selling the first stock on day i.
  • buy2[i]: Maximum profit after buying the second stock on day i.
  • sell2[i]: Maximum profit after selling the second stock on day i.

For each day, we have the following state transitions:

  • buy1[i] = max(buy1[i-1], -prices[i]): Either keep the previous state or buy the first stock.
  • sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i]): Either keep the previous state or sell the first stock.
  • buy2[i] = max(buy2[i-1], sell1[i-1] - prices[i]): Either keep the previous state or buy the second stock using the profit from the first transaction.
  • sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i]): Either keep the previous state or sell the second stock.

At the end, sell2[n-1] will represent the maximum profit after at most two transactions.

Algorithm:

  1. Initialize arrays buy1, sell1, buy2, and sell2 of size n.
  2. Set buy1[0] = -prices[0], sell1[0] = 0, buy2[0] = -prices[0], and sell2[0] = 0.
  3. Iterate through the prices array starting from the second day (i = 1):
  4. a. Update buy1[i] = max(buy1[i-1], -prices[i]).
  5. b. Update sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i]).
  6. c. Update buy2[i] = max(buy2[i-1], sell1[i-1] - prices[i]).
  7. d. Update sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i]).
  8. Return sell2[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 four arrays of size n to store the maximum profit for each state at each day.

Approach 3: Split and Conquer Approach

A different approach is to split the problem into two parts: finding the maximum profit for a single transaction on the left side and on the right side of each day.

For each day, we calculate:

  • The maximum profit we can get from a single transaction on days 0 to i.
  • The maximum profit we can get from a single transaction on days i to n-1.

Then, for each day, we calculate the maximum profit we can get by doing one transaction before that day and one transaction after that day. The maximum of these values will be our answer.

Algorithm:

  1. Initialize an array leftProfit of size n to store the maximum profit from a single transaction on days 0 to i.
  2. Initialize an array rightProfit of size n to store the maximum profit from a single transaction on days i to n-1.
  3. Calculate leftProfit:
  4. a. Set minPrice = prices[0] and leftProfit[0] = 0.
  5. b. Iterate from i = 1 to n-1:
  6. i. Update minPrice = min(minPrice, prices[i]).
  7. ii. Update leftProfit[i] = max(leftProfit[i-1], prices[i] - minPrice).
  8. Calculate rightProfit:
  9. a. Set maxPrice = prices[n-1] and rightProfit[n-1] = 0.
  10. b. Iterate from i = n-2 down to 0:
  11. i. Update maxPrice = max(maxPrice, prices[i]).
  12. ii. Update rightProfit[i] = max(rightProfit[i+1], maxPrice - prices[i]).
  13. Find the maximum combined profit:
  14. a. Initialize maxProfit = 0.
  15. b. Iterate from i = 0 to n-1:
  16. i. Update maxProfit = max(maxProfit, leftProfit[i] + rightProfit[i]).
  17. Return maxProfit as the maximum profit.

Time Complexity:

O(n)

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

Space Complexity:

O(n)

We use two arrays of size n to store the maximum profit for each day.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function maxProfit(prices):
    n = length of prices
    if n <= 1:
        return 0
 
    buy1 = -prices[0]
    sell1 = 0
    buy2 = -prices[0]
    sell2 = 0
 
    for i from 1 to n-1:
        buy1 = max(buy1, -prices[i])
        sell1 = max(sell1, buy1 + prices[i])
        buy2 = max(buy2, sell1 - prices[i])
        sell2 = max(sell2, buy2 + prices[i])
 
    return sell2
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone