Python – Calculate Maximum Profit by Buying and Selling Stock at Most Twice Using an Array

This problem involves determining the maximum profit from buying and selling stock at most twice. Given an array of stock prices where each element represents the price on a particular day, the goal is to calculate the maximum profit by making at most two transactions. A transaction consists of buying one share and later selling that share.

This tutorial explains the problem, provides sample inputs and outputs, outlines the solution steps, and presents a Python program to solve the problem.

Problem Statement

Given an array prices of length n, where prices[i] is the price of a stock on day i, calculate the maximum profit achievable by completing at most two transactions. Note that you must sell the stock before buying again, and if no profit is possible, the maximum profit should be 0.

Sample Input and Output

Example 1:

</>
Copy
# Sample Input
prices = [3, 3, 5, 0, 0, 3, 1, 4]

# Sample Output
# Maximum profit is 6:
#   Transaction 1: Buy at 0 and sell at 3 (profit = 3)
#   Transaction 2: Buy at 1 and sell at 4 (profit = 3)
#   Total Profit = 3 + 3 = 6

Example 2:

</>
Copy
# Sample Input
prices = [1, 2, 3, 4, 5]

# Sample Output
# Maximum profit is 4:
#   Transaction 1: Buy at 1 and sell at 5 (profit = 4)
#   Only one transaction is needed.

Solution Approach

We can solve this problem with a two-pass algorithm:

  1. First Pass (Left to Right):
    • Track the minimum price seen so far.
    • Compute the maximum profit that can be made by selling on each day.
    • Store the profit for each day in an array (left_profits).
  2. Second Pass (Right to Left):
    • Track the maximum price from the right.
    • Compute the maximum profit that can be made by buying on each day.
    • Store this profit for each day in another array (right_profits).
  3. Combine:
    • For each day, the sum of the maximum profit from the left side and right side gives the total profit if the two transactions were split at that day.
    • The maximum combined profit across all days is the answer.

Python Program

</>
Copy
def max_profit_two_transactions(prices):
    if not prices:
        return 0

    n = len(prices)
    # Array to store maximum profit if sold on or before day i
    left_profits = [0] * n  
    # Array to store maximum profit if bought on or after day i
    right_profits = [0] * n  

    # First Pass: Calculate max profit from 0 to i (one transaction)
    min_price = prices[0]
    for i in range(1, n):
        min_price = min(min_price, prices[i])
        left_profits[i] = max(left_profits[i - 1], prices[i] - min_price)

    # Second Pass: Calculate max profit from i to n-1 (one transaction)
    max_price = prices[-1]
    for i in range(n - 2, -1, -1):
        max_price = max(max_price, prices[i])
        right_profits[i] = max(right_profits[i + 1], max_price - prices[i])

    # Combine the two transactions for maximum profit
    max_profit = 0
    for i in range(n):
        max_profit = max(max_profit, left_profits[i] + right_profits[i])

    return max_profit

# Example usage:
prices1 = [3, 3, 5, 0, 0, 3, 1, 4]
print("Maximum Profit (Example 1):", max_profit_two_transactions(prices1))

prices2 = [1, 2, 3, 4, 5]
print("Maximum Profit (Example 2):", max_profit_two_transactions(prices2))

Conclusion

This tutorial demonstrated how to calculate the maximum profit from buying and selling stock at most twice using an array. We approached the problem by breaking it into two passes: one to compute the maximum profit up to each day and another to compute the maximum profit from each day onward. Combining these results gives an efficient solution with a time complexity of O(n) and space complexity of O(n), making it a solid approach for DSA interviews.