#123

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Best Time to Buy and Sell Stock III

Determine the maximum profit from at most two stock transactions using state transition dynamic programming on price arrays.

array dynamic programming

Problem Statement

You are given an array of integers where each element represents the price of a stock on a specific day. You can perform at most two transactions, meaning you can buy and sell the stock twice at most. Each transaction must consist of a buy followed by a sell, and you cannot hold multiple stocks at once.

Your goal is to find the maximum total profit achievable under these rules. Ensure that each transaction is non-overlapping, and consider the optimal combination of the two transactions across all days.

Examples

Example 1

Input: prices = [3,3,5,0,0,3,1,4]

Output: 6

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

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

In this case, no transaction is done, i.e. max profit = 0.

Constraints

1 <= prices.length <= 105
0 <= prices[i] <= 105

Solution Approach

Define State Transitions

Model four states: first buy, first sell, second buy, and second sell. Each state depends on the previous day’s state, capturing the best profit possible while respecting the at-most-two-transactions rule.

Iterate Through Prices

Traverse the price array, updating each state based on whether you buy or sell on that day. For example, first buy is the max of previous first buy and negative current price, while first sell is the max of previous first sell and first buy plus current price.

Return Maximum Profit

After processing all days, the maximum profit is the value of the second sell state, representing the profit after completing up to two optimal transactions without overlap.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each day updates a fixed number of states. Space complexity is O(1) because only four variables are maintained instead of storing all intermediate states.

What Interviewers Usually Probe

Look for correct handling of up to two transactions without simultaneous holds.
Check if state transitions correctly track buy and sell decisions for both transactions.
Watch for off-by-one errors when updating profits across days.

Common Pitfalls or Variants

Common pitfalls

Attempting to store profits for all transaction counts in an array can increase space unnecessarily.
Overwriting states in the wrong order can cause incorrect profit calculations.
Failing to consider zero transactions as a valid maximum profit scenario.

Follow-up variants

At most k transactions instead of two, requiring generalized DP with k states.
Allowing transaction fees, adjusting state updates to subtract fees when selling.
Restricting cooldown days between transactions, requiring extra states to track cooldown.

FAQ

What is the main strategy for Best Time to Buy and Sell Stock III?

Use state transition dynamic programming with four states: first buy, first sell, second buy, and second sell, iterating through prices to maximize profit.

Can I complete multiple transactions simultaneously?

No, each buy must be followed by a sell before initiating the next transaction.

What if the price array is strictly decreasing?

In that case, no transactions should be made, and the maximum profit is 0.

How does GhostInterview prevent common DP mistakes?

It tracks state updates in order, preventing overwriting and ensuring each transaction is counted correctly.

Is this approach scalable for large arrays?

Yes, it runs in O(n) time and O(1) space, making it efficient even for arrays up to 105 elements.

terminal

Solution

Solution 1: Dynamic Programming

We define the following variables:

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#122 best time to buy and sell stock ii #121 best time to buy and sell stock #120 triangle