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).

Note

A transaction is a buy & a sell. You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Examples

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.

Solution

Method 1 - Using Best Time to Buy and Sell Stock Only Once

We can use Best Time To Buy And Sell Stock 1 - only one transaction solution.

A straightforward approach is to evaluate each index i and compute:

Max profit with at most two transactions =
	MAX {max profit using one transaction in subarray prices[0..i] +
		 max profit using one transaction in subarray prices[i+1..n-1] }
for each i from 0 to n-1.

The maximum possible profit from one transaction can be calculated using an O(n) algorithm.

The time complexity of this approach is O(n^2).

Method 2 - Divide and Conquer With Scanning From Left and Right to Calculate Max Profit

We can enhance Method 1 to develop an efficient O(n) solution.

The concept is to record the maximum possible profit for each subarray and solve the problem in two phases:

  1. Create a table profit[0..n-1] and initialize all its values to 0.
  2. Traverse prices[] from right to left, updating profit[i] so it stores the maximum profit achievable from one transaction in the subarray prices[i..n-1].
  3. Traverse prices[] from left to right, updating profit[i] so it represents the maximum profit achievable with two transactions in the subarray prices[0..i].
  4. Return profit[n-1].

For step 1, keep track of the maximum price from right to left. For step 2, monitor the minimum price from left to right. Why traverse in reverse directions? This approach saves space by using the same array to store both the maximum profit from one transaction and the maximum profit from two transactions. After iteration i, profit[0..i] contains the maximum profit with two transactions, and profit[i+1..n-1] contains the maximum profit with one transaction.

Below are implementations of this approach.

Here are the steps:

  1. First Phase: Calculate the maximum profit achievable from one transaction for each i in the subarray prices[i..n-1].
    • Initialize maxPrice to the last price.
    • Traverse the array backwards to update maxPrice and calculate the maximum profit at each step.
  2. Second Phase: Calculate the maximum profit achievable with two transactions for each i in the subarray prices[0..i].
    • Initialize minPrice to the first price.
    • Traverse the array forwards to update minPrice and calculate the maximum profit at each step.
  3. Final Result: The value profit[n-1] contains the maximum profit with at most two transactions.

Code

Java
public class Solution {
    public int maxProfit(int prices[]) {
        int n = prices.length;
        int[] profit = new int[n];

        // Calculate maximum profit with one transaction in the subarray
        // prices[i..n-1]
        int maxPrice = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            maxPrice = Math.max(maxPrice, prices[i]);
            profit[i] = Math.max(profit[i + 1], maxPrice - prices[i]);
        }

        // Calculate the maximum profit with two transactions in the subarray
        // prices[0..i]
        int minPrice = prices[0];
        for (int i = 1; i < n; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            profit[i] =
                Math.max(profit[i - 1], profit[i] + (prices[i] - minPrice));
        }

        return profit[n - 1];
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 3 - Using Two Separate Left and Array Matrix Instead of Using Profit Array

We will use two arrays in the proposed solution:

  • left[i] = the maximum profit achievable by buying and selling in the interval [0, i]. If selling happens at time j (with j in [0, i]), the purchase should be at the minimum price between 0 and j.
  • right[i] = the maximum profit achievable by buying and selling in the interval [i, n-1]. If buying happens at time j (with j in [i, n-1]), the sale should be at the maximum price between j and n-1.

To determine the best point i to separate the two transactions, we need to maximize the combination left[i] + right[i]. This involves evaluating all possible values of i.

We use left[i] to keep track of the maximum profit for transactions up to i, and right[i] for transactions after i. Here’s an example to illustrate:

Prices: 1 4 5 7 6 3 2 9
left  = [0, 3, 4, 6, 6, 6, 6, 8]
right = [8, 7, 7, 7, 7, 7, 7, 0]
sum   = [8, 10, 11, 13, 13, 13, 13, 13]
Ans   = sum[n-1] = 13

Code

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

	//highest profit in 0 ... i
	int[] left = new int[prices.length];
	int[] right = new int[prices.length];

	// DP from left to right
	left[0] = 0;
	int min = prices[0];
	for (int i = 1; i < prices.length; i++) {
		min = Math.min(min, prices[i]);
		left[i] = Math.max(left[i - 1], prices[i] - min);
	}

	// DP from right to left
	right[prices.length - 1] = 0;
	int max = prices[prices.length - 1];
	for (int i = prices.length - 2; i >= 0; i--) {
		max = Math.max(max, prices[i]);
		right[i] = Math.max(right[i + 1], max - prices[i]);
	}

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

	return profit;
}

Method 4 - Multiple DP Solution Using at Most K Transcation

We can also approach this problem with dynamic programming. Suppose we are allowed to make up to k transactions instead of just 2. Then this problem becomes - Best Time To Buy And Sell Stock 4 - at most k times