Best Time to Buy and Sell Stock III

You are given an array prices where prices[i] is the price of a given stock on the i<sup>th</sup> day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:

• 1 <= prices.length <= 10<sup>5</sup>
• 0 <= prices[i] <= 10<sup>5</sup>

def max_profit(prices):
    """Calculates the maximum profit that can be achieved with at most two transactions.

    Args:
        prices (list[int]): A list of integers representing the price of a stock on each day.

    Returns:
        int: The maximum profit that can be achieved.
    """
    n = len(prices)
    if n < 2:
        return 0

    # dp[i][j] represents the maximum profit up to day i with at most j transactions
    dp = [[0] * 3 for _ in range(n)]

    for j in range(1, 3):
        max_so_far = -prices[0]
        for i in range(1, n):
            dp[i][j] = max(dp[i-1][j], prices[i] + max_so_far)
            max_so_far = max(max_so_far, dp[i-1][j-1] - prices[i])

    return dp[n-1][2]


# Example usage
prices1 = [3, 3, 5, 0, 0, 3, 1, 4]
print(f"Maximum profit for {prices1}: {max_profit(prices1)}")  # Output: 6

prices2 = [1, 2, 3, 4, 5]
print(f"Maximum profit for {prices2}: {max_profit(prices2)}")  # Output: 4

prices3 = [7, 6, 4, 3, 1]
print(f"Maximum profit for {prices3}: {max_profit(prices3)}")  # Output: 0

Explanation:

The problem requires finding the maximum profit achievable with at most two transactions in a given array of stock prices. A dynamic programming approach can efficiently solve this.

1. Naive Approach (Brute Force):

   • A brute-force approach would involve trying all possible pairs of transactions. This is highly inefficient, with a time complexity of O(n^2) or higher, where n is the number of days.

2. Optimal Solution (Dynamic Programming):

   • We use dynamic programming to solve this problem more efficiently.
   • We define dp[i][j] as the maximum profit up to day i with at most j transactions.
   • The core idea is to iterate through the days and transactions, updating the dp table based on whether we make a transaction on that day or not.
   • The recurrence relation can be described as:
     • dp[i][j] = max(dp[i-1][j], prices[i] + max_so_far)
     • max_so_far = max(max_so_far, dp[i-1][j-1] - prices[i])
   • dp[i-1][j] means we don't make a transaction on day i.
   • prices[i] + max_so_far means we sell on day i, and max_so_far keeps track of the maximum profit we can get from buying before day i.

Big(O) Run-time Analysis:

• The algorithm uses nested loops. The outer loop runs for a constant number of transactions (at most 2), and the inner loop iterates through the n days.
• Therefore, the time complexity is O(n), where n is the number of days (length of the prices array).

Big(O) Space Usage Analysis:

• We use a 2D DP table of size n x 3 where n is the length of prices array.
• Thus, the space complexity is O(n).

Edge Cases:

• Empty or single-day prices: If the prices array is empty or contains only one day, no transaction can be made, and the profit is 0.
• Decreasing prices: If the prices are continuously decreasing, no transaction will yield a profit, so the maximum profit remains 0.
• Increasing prices: If the prices are continuously increasing, one transaction (buy on the first day, sell on the last day) might be the most profitable, or two transactions might be better depending on the price variations.