Practice/Oracle/Leetcode 123. Best Time to Buy and Sell Stock III

Leetcode 123. Best Time to Buy and Sell Stock III

CodingOptional

Problem

You are given an array where each element represents the price of a stock on a particular day. Your goal is to determine the maximum profit you can achieve by completing at most two separate buy-sell transactions.

Important rules:

• You must sell your stock before you can purchase it again (transactions cannot overlap)
• You may choose to complete zero, one, or two transactions
• Each transaction consists of buying on one day and selling on a later day

Return the maximum profit that can be obtained.

Requirements

1. Handle arrays with at least one element (minimum length is 1)
2. All prices are non-negative integers
3. You can complete 0, 1, or 2 transactions (not required to use both)
4. Transactions must be completed sequentially (sell before the next buy)
5. Return 0 if no profit is possible

Constraints

• 1 ≤ prices.length ≤ 100,000
• 0 ≤ prices[i] ≤ 100,000
• Expected time complexity: O(n)
• Expected space complexity: O(1) or O(n)

Examples

Example 1:

Input: prices = [3, 3, 5, 0, 0, 3, 1, 4] Output: 6 Explanation: Purchase on day 4 (price = 0), sell on day 6 (price = 3), profit = 3. Then purchase 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: Purchase on day 1 (price = 1) and sell on day 5 (price = 5). Profit = 4. A second transaction isn't beneficial.

Example 3:

Input: prices = [7, 6, 4, 3, 1] Output: 0 Explanation: Prices only decrease, so no profitable transaction exists.

Example 4:

Input: prices = [1, 4, 2, 7, 3, 9] Output: 12 Explanation: Purchase on day 1 (price = 1), sell on day 4 (price = 7), profit = 6. Then purchase on day 5 (price = 3), sell on day 6 (price = 9), profit = 6. Total profit = 6 + 6 = 12.