Best Time to Buy and Sell Stock III

Problem Description

You are given an array prices where prices[i] is the price of a given stock on the i-th 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).

Key Insights

• You can make at most two transactions (buy and sell).
• The transactions must be completed in sequence: sell before you buy again.
• The problem can be broken down into two parts: the first transaction and the second transaction.
• Dynamic programming can be used to track profits on each transaction up to two transactions.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a dynamic programming approach where we maintain two variables for each transaction: the minimum price seen so far and the maximum profit. We will iterate through the prices array twice, once for the first transaction and once for the second transaction, keeping track of the maximum profits at each stage.

1. We initialize variables to track the minimum price and maximum profit for the first and second transactions.
2. Iterate through the prices array to compute the maximum profit for the first transaction.
3. Iterate again to compute the maximum profit for the second transaction, considering the profits from the first transaction.
4. Return the maximum profit achieved from both transactions.

Code Solutions