Problem statement

You are given an array prices where prices[i] is the price of a stock on day i.

Find the maximum profit achievable with at most two transactions. You may not hold two shares at once — a purchase must be sold before the next purchase.

Example 1

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy at 0 and sell at 3, then buy at 1 and sell at 4.

Example 2

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: One transaction across the whole rise is best.

Example 3

Input: prices = [7,6,4,3,1]
Output: 0

Constraints

• 1 <= prices.length <= 40
• 0 <= prices[i] <= 1000

Hints for Best Time to Buy and Sell Stock III

1. Hint 1

   Carry four running best values: after the first buy, first sell, second buy and second sell.

2. Hint 2

   Each day, update them in that order — the second buy is funded by whatever the first sale earned.

3. Hint 3

   Because each value depends only on values already updated this day, a single pass is correct.

How to solve Best Time to Buy and Sell Stock III

Carry four running values — after first buy, first sell, second buy, second sell — and update them in that order each day so the second purchase is funded by the first sale.

Approach

1. Initialise buy1 = buy2 = -∞, sell1 = sell2 = 0.
2. For each price: buy1 = max(buy1, -price), sell1 = max(sell1, buy1 + price), buy2 = max(buy2, sell1 - price), sell2 = max(sell2, buy2 + price).
3. Return sell2.

Why it works

The four values are the best profit reachable in each of the four transaction stages after processing the prefix. Updating in stage order within a day is safe: a same-day buy-and-sell nets zero and never beats the alternative.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• The general k-transaction version repeats the pair of updates k times per day.

Reference solution

Python

def maxProfit(prices) -> int:
    buy1 = buy2 = float("-inf")
    sell1 = sell2 = 0
    for price in prices:
        buy1 = max(buy1, -price)
        sell1 = max(sell1, buy1 + price)
        buy2 = max(buy2, sell1 - price)
        sell2 = max(sell2, buy2 + price)
    return sell2

Java

public static int maxProfit(int[] prices) {
    int buy1 = -1000000, sell1 = 0, buy2 = -1000000, sell2 = 0;
    for (int price : prices) {
        buy1 = Math.max(buy1, -price);
        sell1 = Math.max(sell1, buy1 + price);
        buy2 = Math.max(buy2, sell1 - price);
        sell2 = Math.max(sell2, buy2 + price);
    }
    return sell2;
}

C++

int maxProfit(vector<int>& prices) {
    int buy1 = -1000000, sell1 = 0, buy2 = -1000000, sell2 = 0;
    for (int price : prices) {
        buy1 = max(buy1, -price);
        sell1 = max(sell1, buy1 + price);
        buy2 = max(buy2, sell1 - price);
        sell2 = max(sell2, buy2 + price);
    }
    return sell2;
}

JavaScript

var maxProfit = function(prices) {
    let buy1 = -Infinity, sell1 = 0, buy2 = -Infinity, sell2 = 0;
    for (let i = 0; i < prices.length; i++) {
        buy1 = Math.max(buy1, -prices[i]);
        sell1 = Math.max(sell1, buy1 + prices[i]);
        buy2 = Math.max(buy2, sell1 - prices[i]);
        sell2 = Math.max(sell2, buy2 + prices[i]);
    }
    return sell2;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard