Maximum Profit with At Most Two Transactions

Problem Description

You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete at most two transactions. Note that you may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Naive Approach

A brute-force solution involves trying every possible combination of buy and sell days for at most two transactions and calculating the profit. This approach explores all possible subarrays and checks if the profit from two transactions is greater than the current maximum.

Code (Brute Force - Python)

def max_profit_brute_force(prices):
    max_profit = 0
    n = len(prices)
    
    for i in range(n):
        for j in range(i + 1, n):
            profit1 = prices[j] - prices[i]
            if profit1 > 0:
                max_profit = max(max_profit, profit1)
                for k in range(j + 1, n):
                    for l in range(k + 1, n):
                        profit2 = prices[l] - prices[k]
                        if profit2 > 0:
                            max_profit = max(max_profit, profit1 + profit2)
    return max_profit

Time Complexity: O(n^4)

Space Complexity: O(1)

This approach is highly inefficient due to its nested loops, making it impractical for large input sizes.

Optimal Approach (Dynamic Programming)

A more efficient approach uses dynamic programming. We can define dp[i][j] as the maximum profit achievable with at most j transactions up to day i. We can optimize the space complexity further.

Algorithm

1. Initialize buy1, sell1, buy2, and sell2 to track the states of buying and selling.
2. Iterate through the prices array.
3. Update buy1 to minimize the cost of the first buy.
4. Update sell1 to maximize the profit after the first sell.
5. Update buy2 to maximize the profit after the first transaction and the cost of the second buy.
6. Update sell2 to maximize the overall profit after two transactions.

Code (Optimal - Python)

def max_profit_optimal(prices):
    buy1 = buy2 = float('inf')
    sell1 = sell2 = 0
    
    for price in prices:
        buy1 = min(buy1, price)
        sell1 = max(sell1, price - buy1)
        buy2 = min(buy2, price - sell1)
        sell2 = max(sell2, price - buy2)
        
    return sell2

Time Complexity: O(n)

Space Complexity: O(1)

Edge Cases

• If the prices array is empty or has only one element, the maximum profit is 0.
• If the prices are constantly decreasing, the maximum profit is 0.

Explanation

The optimal solution efficiently calculates the maximum profit by keeping track of the minimum buying prices and maximum selling prices for up to two transactions. This eliminates the need for nested loops, resulting in a linear time complexity.