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.

Maximize Stock Profit — Part A: At Most One Transaction

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 a single day to buy one stock and choosing a different day in the future to sell that stock. You are allowed to complete at most one transaction (buy once and sell once).

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, 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. Note that buying on day 1 and selling on day 0 is not allowed because you must buy before you sell.

Approach: Track the minimum price seen so far while scanning left to right; at each day the best profit ending today is price − min_so_far. Keep the maximum over all days.

Constraints

• 1 <= n <= 10^5, where n = prices.length
• 0 <= prices[i] <= 10^4
• You must buy before you sell (sell day strictly after buy day)
• At most one transaction

Hints

1. You only ever care about the lowest price you've seen so far when deciding where to sell today.
2. Scan once, maintaining the running minimum price and the best profit (current price minus running minimum).
3. If prices only decrease, no profitable transaction exists, so the answer is 0.

Maximize Stock Profit — Part B: At Most Two Transactions

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

You are now allowed to complete at most two transactions. Each transaction is a buy followed by a sell. You must sell the stock before you can buy again (you may not hold more than one share at a 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) for profit 3; then buy on day 6 (price = 1), sell on day 7 (price = 4) for profit 3. Total = 6.

Approach: Track four running values as you scan: buy1 (lowest effective cost of the first buy), profit1 (best profit after one sell), buy2 (lowest effective cost of the second buy, net of profit1), and profit2 (best total profit after the second sell). Each is updated in O(1) per day, giving O(n) time and O(1) space.

Constraints

• 1 <= n <= 10^5, where n = prices.length
• 0 <= prices[i] <= 10^4
• You must sell before buying again (no overlapping transactions)
• At most two transactions

Hints

1. You can extend the one-transaction state machine: track the best state after buy 1, sell 1, buy 2, and sell 2.
2. For the second buy, treat its effective cost as the current price minus the profit already locked in from the first transaction.
3. Update all four states in a single left-to-right pass; the answer is the best profit after the second sell.
4. If only one transaction is profitable, the second-transaction states naturally collapse so the answer still reflects at most two trades.