{x}
blog image

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 ith 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 <= 105
  • 0 <= prices[i] <= 105

Solution Explanation: 123. Best Time to Buy and Sell Stock III

This problem asks to find the maximum profit achievable from at most two transactions on a given stock price array. We can solve this efficiently using dynamic programming.

Approach: Dynamic Programming

Instead of considering all possible combinations of buying and selling, we use dynamic programming to build up the solution iteratively. We define four variables to track the maximum profit at each stage:

  • f1: Maximum profit after the first buy (but before the first sell). It's initialized to -prices[0] because buying the stock on day 0 incurs a cost.
  • f2: Maximum profit after the first buy and first sell. It's initialized to 0 as we haven't sold yet.
  • f3: Maximum profit after the second buy (but before the second sell). It's initialized to -prices[0], similar to f1.
  • f4: Maximum profit after the second buy and second sell. It's initialized to 0.

We iterate through the prices array. For each price:

  1. Update f1: The maximum profit after the first buy is either the previous f1 (if we didn't buy today) or the negative of the current price (if we bought today). We choose the maximum.

  2. Update f2: The maximum profit after the first buy and sell is either the previous f2 or the profit from selling today (f1 + prices[i]).

  3. Update f3: The maximum profit after the second buy is either the previous f3 or the profit from buying today after the first transaction (f2 - prices[i]).

  4. Update f4: The maximum profit after the second buy and sell is either the previous f4 or the profit from selling today (f3 + prices[i]).

Finally, f4 holds the maximum profit achievable from at most two transactions.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the prices array. We iterate through the array once.
  • Space Complexity: O(1). We use a constant number of variables to store the intermediate results.

Code Implementation (Python)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
 
        f1 = -prices[0]  # Max profit after first buy
        f2 = 0           # Max profit after first buy and sell
        f3 = -prices[0]  # Max profit after second buy
        f4 = 0           # Max profit after second buy and sell
 
        for i in range(1, len(prices)):
            f1 = max(f1, -prices[i])
            f2 = max(f2, f1 + prices[i])
            f3 = max(f3, f2 - prices[i])
            f4 = max(f4, f3 + prices[i])
 
        return f4

The implementations in other languages (Java, C++, Go, TypeScript, Rust, C#) follow the same logic, just using their respective syntax for array access, max functions, and variable declarations. The core dynamic programming algorithm remains identical.