Problem Description

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

Your goal is to find the maximum profit you can achieve by completing at most two transactions. A transaction consists of buying and then selling one share of the stock.

Important constraints:

• You can complete at most 2 transactions (buy-sell pairs)
• You cannot hold multiple stocks at the same time - you must sell your current stock before buying again
• You cannot sell a stock before buying it

The solution uses dynamic programming with four state variables:

• f1: Maximum profit after completing the first buy operation
• f2: Maximum profit after completing the first sell operation
• f3: Maximum profit after completing the second buy operation
• f4: Maximum profit after completing the second sell operation

For each day's price, the code updates these states:

• f1 = max(f1, -price): Either keep the previous buy state or buy at today's price
• f2 = max(f2, f1 + price): Either keep the previous first-sell state or sell the first stock today
• f3 = max(f3, f2 - price): Either keep the previous second-buy state or buy the second stock today using profit from first transaction
• f4 = max(f4, f3 + price): Either keep the previous second-sell state or sell the second stock today

The final answer is f4, which represents the maximum profit after completing at most two transactions.

Intuition

The key insight is that with at most two transactions, we need to track the best profit at each possible stage of trading. Since we can't hold multiple stocks simultaneously, our trading follows a strict sequence: buy → sell → buy → sell.

At any point in time, we can be in one of four states:

1. After first buy (holding first stock)
2. After first sell (completed one transaction, holding cash)
3. After second buy (holding second stock)
4. After second sell (completed two transactions)

The challenge is determining when to make each move to maximize profit. For each day, we need to decide: should we maintain our current state or transition to the next state?

This naturally leads to a dynamic programming approach where we track the maximum profit achievable at each state. The transitions are:

• To buy first stock: We spend price, so profit becomes -price
• To sell first stock: We gain price added to our profit from buying
• To buy second stock: We spend price from our first transaction's profit
• To sell second stock: We gain price added to our second buy profit

The beauty of this approach is that we don't need to explicitly track which days we buy and sell. Instead, we just maintain the best possible profit at each state as we process each day. If buying or selling on a particular day doesn't improve our profit, we simply keep the previous state's value.

By considering all prices sequentially and updating our four states optimally, we ensure we capture the maximum profit possible with at most two transactions. The final answer is f4 because it represents the state after completing all possible transactions.

Solution Approach

The solution implements a state-based dynamic programming approach with four variables representing different trading states.

Initialization: We start by initializing the four state variables:

• f1 = -prices[0]: After buying the first stock on day 0, our profit is negative (we spent money)
• f2 = 0: We haven't sold anything yet, so profit is 0
• f3 = -prices[0]: If we were to buy a second stock on day 0 (hypothetically after a zero-profit first transaction)
• f4 = 0: No second sale yet, profit is 0

State Transitions: For each subsequent day (starting from day 1), we update all four states:

1. First Buy (f1):

   • f1 = max(f1, -price)
   • Either keep the previous buy state (we already bought earlier at a better price) or buy today (starting fresh with -price profit)

2. First Sell (f2):

   • f2 = max(f2, f1 + price)
   • Either keep the previous sell state (we already sold at a better price) or sell today (adding today's price to our first buy profit)

3. Second Buy (f3):

   • f3 = max(f3, f2 - price)
   • Either keep the previous second buy state or buy today using profits from the first transaction (f2 - price)

4. Second Sell (f4):

   • f4 = max(f4, f3 + price)
   • Either keep the previous second sell state or sell today (adding today's price to our second buy profit)

Why This Works: The algorithm ensures that at each step, we maintain the maximum possible profit for each state. The max operations guarantee we only transition to a new state if it's profitable. If completing fewer than two transactions yields better profit, the algorithm naturally handles this - f4 will simply equal f2 (the profit from one transaction).

Time and Space Complexity:

• Time: O(n) where n is the length of the prices array (single pass)
• Space: O(1) using only four variables regardless of input size

The final answer f4 represents the maximum profit achievable with at most two complete transactions.

Example Walkthrough

Let's walk through the algorithm with prices = [3, 2, 6, 5, 0, 3].

Initial Setup (Day 0, price = 3):

• f1 = -3 (bought first stock at price 3)
• f2 = 0 (haven't sold yet)
• f3 = -3 (hypothetical second buy)
• f4 = 0 (haven't completed second transaction)

Day 1 (price = 2):

• f1 = max(-3, -2) = -2 (better to buy at price 2)
• f2 = max(0, -3 + 2) = 0 (selling would give -1 profit, so don't sell)
• f3 = max(-3, 0 - 2) = -2 (better to buy second stock now)
• f4 = max(0, -3 + 2) = 0 (selling would give -1, so don't sell)

Day 2 (price = 6):

• f1 = max(-2, -6) = -2 (keep previous buy at price 2)
• f2 = max(0, -2 + 6) = 4 (sell first stock for profit of 4)
• f3 = max(-2, 0 - 6) = -2 (keep previous second buy)
• f4 = max(0, -2 + 6) = 4 (could sell second stock for profit of 4)

Day 3 (price = 5):

• f1 = max(-2, -5) = -2 (keep buy at price 2)
• f2 = max(4, -2 + 5) = 4 (previous sell at 6 was better)
• f3 = max(-2, 4 - 5) = -1 (buy second stock using first transaction's profit)
• f4 = max(4, -2 + 5) = 4 (keep previous state)

Day 4 (price = 0):

• f1 = max(-2, -0) = 0 (buying at 0 is better)
• f2 = max(4, -2 + 0) = 4 (keep previous sell)
• f3 = max(-1, 4 - 0) = 4 (buy second stock at price 0 using profit of 4)
• f4 = max(4, -1 + 0) = 4 (keep previous state)

Day 5 (price = 3):

• f1 = max(0, -3) = 0 (keep buy at price 0)
• f2 = max(4, 0 + 3) = 4 (keep previous sell)
• f3 = max(4, 4 - 3) = 4 (keep second buy at price 0)
• f4 = max(4, 4 + 3) = 7 (sell second stock for total profit of 7)

Final Result: 7

The optimal strategy was:

• First transaction: Buy at price 2 (day 1), sell at price 6 (day 2) → profit = 4
• Second transaction: Buy at price 0 (day 4), sell at price 3 (day 5) → profit = 3
• Total profit = 4 + 3 = 7

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the prices array. The algorithm iterates through the prices array once using a single for loop that runs from index 1 to the end of the array. Each iteration performs a constant number of operations (four max comparisons and arithmetic operations), resulting in linear time complexity.

Space Complexity: O(1). The algorithm uses only four variables (f1, f2, f3, f4) to track the states of buying and selling stocks, regardless of the input size. No additional data structures that scale with input size are used, making the space complexity constant.

Common Pitfalls

1. Incorrect State Update Order

A critical pitfall is updating the state variables in the wrong order within the loop, which causes the algorithm to use already-updated values from the current iteration instead of values from the previous iteration.

Problematic Code:

for price in prices[1:]:
    first_buy = max(first_buy, -price)
    first_sell = max(first_sell, first_buy + price)  # Uses updated first_buy!
    second_buy = max(second_buy, first_sell - price)  # Uses updated first_sell!
    second_sell = max(second_sell, second_buy + price)  # Uses updated second_buy!

Why This Is Wrong: When we update first_sell, we're using the first_buy value that was just updated in the same iteration. This means we could potentially be buying and selling on the same day, which violates the problem constraints.

Solution: Update states in reverse order or use temporary variables:

# Option 1: Reverse order updates
for price in prices[1:]:
    second_sell = max(second_sell, second_buy + price)
    second_buy = max(second_buy, first_sell - price)
    first_sell = max(first_sell, first_buy + price)
    first_buy = max(first_buy, -price)

# Option 2: Use temporary variables
for price in prices[1:]:
    new_first_buy = max(first_buy, -price)
    new_first_sell = max(first_sell, first_buy + price)
    new_second_buy = max(second_buy, first_sell - price)
    new_second_sell = max(second_sell, second_buy + price)
  
    first_buy = new_first_buy
    first_sell = new_first_sell
    second_buy = new_second_buy
    second_sell = new_second_sell

2. Misunderstanding the First Buy State

Another common mistake is initializing or updating first_buy incorrectly by thinking it should account for previous profits.

Incorrect:

first_buy = max(first_buy, prev_profit - price)  # Wrong!

Correct:

first_buy = max(first_buy, -price)  # Correct - first buy starts from 0 profit

The first buy always starts from zero profit since it's the beginning of our trading sequence. Only the second buy (second_buy) should consider profits from previous transactions.

3. Edge Case: Single Element Array

Failing to handle arrays with only one price can cause index out of bounds errors if not using the initialization approach shown.

Problematic Approach:

if len(prices) < 2:
    return 0  # Need at least 2 days to make a transaction

Better Solution: The provided solution naturally handles this by initializing all states with prices[0] and then iterating from index 1, which works even for single-element arrays (the loop simply doesn't execute, returning 0).