Best Time to Buy and Sell Stock III

Problem

You are given an array prices where prices[i] is the price of a given stock on the i-th day. You want to maximize your profit by making at most two transactions (a transaction consists of buying then selling one share of stock).

Important rules:

• You may not engage in multiple transactions simultaneously (you must sell the stock before you buy again).
• You can choose to make 0, 1, or 2 transactions.
• Buying and selling on the same day is allowed.

Return the maximum profit you can achieve. If no profit is possible, return 0.

Input / Output Format

Input: An array of integers prices of length n.

Output: A single integer representing the maximum profit.

Examples

Example 1

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price=0), sell on day 6 (price=3), profit=3. Then buy on day 7 (price=1), sell on day 8 (price=4), profit=3. Total profit = 3+3 = 6.

Example 2

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price=1), sell on day 5 (price=5), profit=4. Only one transaction is needed. Total profit = 4.

Example 3

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: Prices only go down, so no profitable transaction is possible. Return 0.

Approach Hints

• Brute force would try every combination of two non-overlapping buy/sell intervals — O(n²) or worse.
• Optimized DP approach: Think about tracking four states at each day:
  • buy1: minimum cost after the first buy
  • sell1: maximum profit after the first sell
  • buy2: maximum profit after the second buy (profit from sell1 minus current price)
  • sell2: maximum profit after the second sell
• Alternatively, think of splitting the array at every possible index and combining the best single-transaction profit from the left segment and the right segment — precompute prefix and suffix max profits.
• Both approaches achieve O(n) time and O(1) or O(n) space.