# Best Time to Buy and Sell Stock III
**Difficulty:** HARD
[External](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii)
Canonical: https://scaleengineer.com/dsa/problems/best-time-to-buy-and-sell-stock-iii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Bolt](https://scaleengineer.com/companies/bolt), [Tekion](https://scaleengineer.com/companies/tekion), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Visa](https://scaleengineer.com/companies/visa), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [PhonePe](https://scaleengineer.com/companies/phonepe), [Groww](https://scaleengineer.com/companies/groww)
---
## Problem
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`

# Approaches
## Brute Force by Splitting the Array
This approach is based on the idea that two non-overlapping transactions can be seen as one transaction in the first part of the time period and another transaction in the second part. We can try every possible split point in the `prices` array. For each split, we calculate the maximum profit from a single transaction in the left subarray and the right subarray and sum them up. The maximum of these sums over all possible splits will be our answer.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Correctly breaks down the problem into a simpler subproblem.
**Cons:** Inefficient and will likely result in a "Time Limit Exceeded" error for large inputs due to its quadratic time complexity.
### Explanation
We iterate through the `prices` array from `i = 0` to `n-1`, where `n` is the number of days. Each index `i` serves as a potential split point. The first transaction occurs in `prices[0...i]` and the second in `prices[i...n-1]`. For each `i`, we need a helper function to find the maximum profit from a single transaction in a given subarray. This is the classic "Best Time to Buy and Sell Stock I" problem. The helper function, let's call it `maxSingleProfit`, iterates through a subarray, keeping track of the minimum price seen so far and the maximum profit that can be achieved. The main loop calculates `maxSingleProfit(prices[0...i]) + maxSingleProfit(prices[i...n-1])` and updates a global maximum profit. This naturally handles the case of a single transaction as well, since for any split, one of the sub-problems could yield a profit of zero.

```java
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) {
            return 0;
        }

        int maxTotalProfit = 0;

        // The loop iterates through all possible split points.
        // The first transaction is in prices[0...i]
        // The second transaction is in prices[i...n-1]
        for (int i = 0; i < n; i++) {
            int profit1 = maxSingleProfit(prices, 0, i);
            int profit2 = maxSingleProfit(prices, i, n - 1);
            maxTotalProfit = Math.max(maxTotalProfit, profit1 + profit2);
        }

        return maxTotalProfit;
    }

    // Helper to calculate max profit from one transaction in a subarray
    private int maxSingleProfit(int[] prices, int start, int end) {
        if (start >= end) {
            return 0;
        }
        int minPrice = prices[start];
        int maxProfit = 0;
        for (int i = start + 1; i <= end; i++) {
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            minPrice = Math.min(minPrice, prices[i]);
        }
        return maxProfit;
    }
}
```
### Algorithm
*   Initialize `max_profit = 0`.
*   Iterate through each day `i` from `0` to `n-1`, considering it as the day the first transaction's period ends and the second one's begins.
*   For each `i`:
    *   Calculate `profit1`, the maximum profit from one transaction in `prices[0...i]`.
    *   Calculate `profit2`, the maximum profit from one transaction in `prices[i...n-1]`.
    *   Update `max_profit = max(max_profit, profit1 + profit2)`.
*   The final `max_profit` is the answer. This also covers the case of a single transaction, as one of the profits can be zero.

## Dynamic Programming with Two Arrays
This approach improves upon the brute-force method by avoiding redundant calculations. Instead of re-calculating the maximum profit for subarrays in each step, we pre-compute them. We use two arrays: `left[i]` stores the maximum profit from a single transaction in `prices[0...i]`, and `right[i]` stores the maximum profit from a single transaction in `prices[i...n-1]`.
**Time:** O(n) · **Space:** O(n)
**Pros:** Much more efficient than the brute-force approach, with linear time complexity.
**Cons:** Requires additional space proportional to the input size.
### Explanation
The core idea is the same: split the problem into two single-transaction problems. The maximum profit for two transactions is `max(left[i] + right[i])` over all possible split points `i`. 

First, we create an array `left` of size `n`. We iterate from left to right to populate it. `left[i]` will hold the maximum profit achievable from one transaction in the subarray `prices[0...i]`. This is done by keeping track of the minimum price found so far.
`left[i] = max(left[i-1], prices[i] - min_price)`

Second, we create an array `right` of size `n`. We iterate from right to left to populate it. `right[i]` will hold the maximum profit from one transaction in `prices[i...n-1]`. This is done by keeping track of the maximum price found so far.
`right[i] = max(right[i+1], max_price - prices[i])`

Finally, we iterate from `i = 0` to `n-1` to find the maximum total profit. The profit for a split at day `i` is `left[i] + right[i]`. The maximum profit can also be from a single transaction, which is `left[n-1]`. This value is also considered in our final loop since `right[n-1]` would be 0.

```java
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) {
            return 0;
        }

        // left[i] = max profit in prices[0...i]
        int[] left = new int[n];
        int minPrice = prices[0];
        for (int i = 1; i < n; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            left[i] = Math.max(left[i - 1], prices[i] - minPrice);
        }

        // right[i] = max profit in prices[i...n-1]
        int[] right = new int[n];
        int maxPrice = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            maxPrice = Math.max(maxPrice, prices[i]);
            right[i] = Math.max(right[i + 1], maxPrice - prices[i]);
        }

        int maxTotalProfit = 0;
        for (int i = 0; i < n; i++) {
            maxTotalProfit = Math.max(maxTotalProfit, left[i] + right[i]);
        }

        return maxTotalProfit;
    }
}
```
### Algorithm
*   Create an array `left` of size `n`.
*   Iterate from `i = 1` to `n-1`. Calculate `left[i]` as the maximum profit in `prices[0...i]`. Keep track of the minimum price seen so far.
*   Create an array `right` of size `n`.
*   Iterate from `i = n-2` down to `0`. Calculate `right[i]` as the maximum profit in `prices[i...n-1]`. Keep track of the maximum price seen so far.
*   Initialize `max_profit = 0`.
*   Iterate from `i = 0` to `n-1`. Update `max_profit = max(max_profit, left[i] + right[i])`.
*   Return `max_profit`.

## One-Pass Dynamic Programming with Constant Space
This is the most optimal approach. It solves the problem in a single pass using dynamic programming with a constant number of variables. We can think of the process as a sequence of four actions: buy first stock, sell first stock, buy second stock, sell second stock. We maintain four variables to track the maximum profit at each of these four stages.
**Time:** O(n) · **Space:** O(1)
**Pros:** Highly efficient in both time and space.; It's a clean and concise solution.
**Cons:** The logic can be less intuitive to grasp initially compared to the splitting approach.
### Explanation
We define four variables to represent the maximum profit after each of the four possible state transitions:
*   `buy1`: The maximum profit after buying the first stock. This is equivalent to the negative of the minimum cost to acquire a stock.
*   `sell1`: The maximum profit after selling the first stock.
*   `buy2`: The maximum profit after buying the second stock. This is the profit from the first sale minus the cost of the second buy.
*   `sell2`: The maximum profit after selling the second stock. This is our final answer.

We iterate through the `prices` array once. In each iteration, we update these four variables based on the current price. The key is that the calculation for a state on day `i` depends on the states from day `i-1`.

The state transition equations for each `price` are:
*   `buy1 = max(buy1, -price)`: We want to buy at the lowest possible price, so we maximize the 'profit' which is negative cost.
*   `sell1 = max(sell1, buy1 + price)`: We want to sell at the highest price relative to our purchase, maximizing the profit.
*   `buy2 = max(buy2, sell1 - price)`: We buy the second stock. The profit `sell1` is available, so the new 'profit' state is `sell1 - price`.
*   `sell2 = max(sell2, buy2 + price)`: We sell the second stock, adding the current price to the profit state `buy2`.

After iterating through all prices, `sell2` will hold the maximum profit achievable with at most two transactions. The logic inherently handles 0, 1, or 2 transactions because the initial profit values are 0.

```java
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int buy1 = Integer.MIN_VALUE;
        int sell1 = 0;
        int buy2 = Integer.MIN_VALUE;
        int sell2 = 0;

        for (int price : prices) {
            // The maximum money we have after buying the 1st stock.
            buy1 = Math.max(buy1, -price);
            // The maximum money we have after selling the 1st stock.
            sell1 = Math.max(sell1, buy1 + price);
            // The maximum money we have after buying the 2nd stock.
            buy2 = Math.max(buy2, sell1 - price);
            // The maximum money we have after selling the 2nd stock.
            sell2 = Math.max(sell2, buy2 + price);
        }

        return sell2;
    }
}
```
### Algorithm
*   Initialize four variables: `buy1 = -infinity`, `sell1 = 0`, `buy2 = -infinity`, `sell2 = 0`.
*   `buy1` represents the max profit after the first buy.
*   `sell1` represents the max profit after the first sell.
*   `buy2` represents the max profit after the second buy.
*   `sell2` represents the max profit after the second sell.
*   Iterate through each `price` in the `prices` array:
    *   Update `buy1 = max(buy1, -price)`.
    *   Update `sell1 = max(sell1, buy1 + price)`.
    *   Update `buy2 = max(buy2, sell1 - price)`.
    *   Update `sell2 = max(sell2, buy2 + price)`.
*   After the loop, `sell2` contains the maximum profit. Return `sell2`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MaxProfit(int[] prices) {
        int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
        for (int i = 1; i < prices.Length; ++i) {
            f1 = Math.Max(f1, -prices[i]);
            f2 = Math.Max(f2, f1 + prices[i]);
            f3 = Math.Max(f3, f2 - prices[i]);
            f4 = Math.Max(f4, f3 + prices[i]);
        }
        return f4;
    }
}
```

### Java

```java
public class Solution { public int MaxProfit ( int [] prices ) { int f1 = - prices [ 0 ], f2 = 0 , f3 = - prices [ 0 ], f4 = 0 ; for ( int i = 1 ; i < prices . Length ; ++ i ) { f1 = Math . Max ( f1 , - prices [ i ]); f2 = Math . Max ( f2 , f1 + prices [ i ]); f3 = Math . Max ( f3 , f2 - prices [ i ]); f4 = Math . Max ( f4 , f3 + prices [ i ]); } return f4 ; } }
```

### CPP

```cpp
class Solution {
public:
  int maxProfit(vector<int> &prices) {
    int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
    for (int i = 1; i < prices.size(); ++i) {
      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;
  }
};

```

### Python

```python
''' - `f1` 表示第一次买入股票后的最大利润； - `f2` 表示第一次卖出股票后的最大利润； - `f3` 表示第二次买入股票后的最大利润； - `f4` 表示第二次卖出股票后的最大利润。 ''' class Solution : def maxProfit ( self , prices : List [ int ]) -> int : # 第一次买入，第一次卖出，第二次买入，第二次卖出 f1 , f2 , f3 , f4 = - prices [ 0 ], 0 , - prices [ 0 ], 0 for price in prices [ 1 :]: f1 = max ( f1 , - price ) f2 = max ( f2 , f1 + price ) f3 = max ( f3 , f2 - price ) f4 = max ( f4 , f3 + price ) return f4 class Solution : def maxProfit ( self , prices : List [ int ]) -> int : if not prices : return 0 # 0 to i, max profit left_max = [ 0 ] * len ( prices ) tmp_min = prices [ 0 ] for i in range ( len ( prices )): tmp_min = min ( tmp_min , prices [ i ]) left_max [ i ] = max ( left_max [ i - 1 ], prices [ i ] - tmp_min ) if i > 0 else 0 # i to end, max profit right_max = [ 0 ] * len ( prices ) tmp_max = prices [ - 1 ] for i in range ( len ( prices ) - 1 , - 1 , - 1 ): tmp_max = max ( tmp_max , prices [ i ]) right_max [ i ] = max ( right_max [ i + 1 ], tmp_max - prices [ i ]) if i < len ( prices ) - 1 else 0 return max ( left_max [ i ] + right_max [ i ] for i in range ( len ( prices ))) ############ class Solution ( object ): def maxProfit ( self , prices ): """ :type prices: List[int] :rtype: int """ buy1 = buy2 = float ( "-inf" ) sell1 = sell2 = 0 for i in range ( len ( prices )): sell1 = max ( prices [ i ] + buy1 , sell1 ) buy1 = max ( buy1 , - prices [ i ]) sell2 = max ( sell2 , prices [ i ] + buy2 ) buy2 = max ( sell1 - prices [ i ], buy2 ) return max ( sell1 , sell2 )
```