Maximize stock profit with one or two trades

You are given an array prices where prices[i] is the price of a given stock on day i (0-indexed).

You want to maximize your profit by choosing when to buy and sell this stock, subject to the constraints below. You may not hold more than one share at a time (i.e., you must sell before you can buy again).

Assume:

• 1 <= n <= 10^5, where n = prices.length.
• 0 <= prices[i] <= 10^4.

Part A: At most one transaction

You are allowed to complete at most one transaction (i.e., buy once and sell once).

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

Example

• Input: prices = [7, 1, 5, 3, 6, 4]
• Output: 5
• Explanation: Buy on day 1 (price = 1) and sell on day 4 (price = 6), profit = 6 − 1 = 5.

Part B: At most two transactions

Now you are allowed to complete at most two transactions.

• Each transaction is a buy followed by a sell.
• You must sell the stock before you buy again.
• You cannot engage in multiple transactions at the same time.

Return the maximum total profit you can achieve with at most two transactions.

Example

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

Design algorithms for both parts that run in O(n) time and O(1) or O(n) extra space.