DSA · Dynamic Programming · #39

Best Time to Buy and Sell Stock III

Module 47 · difficulty 4/5·⏱ 30:00starts on first keystroke

You are given an array `prices` where `prices[i]` is the price of a given stock on the `i`-th day. Find the maximum profit you can achieve. You may complete **at most two transactions**. **Note:** You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Implement `maxProfit(prices)` returning the maximum total profit (an integer).

Examples

prices = [3,3,5,0,0,3,1,4] → 6 — 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 = 6.
prices = [1,2,3,4,5] → 4 — Buy on day 1 (price 1), sell on day 5 (price 5), profit 4. Two separate transactions can't beat one full run here.
prices = [7,6,4,3,1] → 0 — Prices only fall, so no transaction is made and profit is 0.

Constraints

· 1 <= prices.length <= 10^5
· 0 <= prices[i] <= 10^5

Session phases

A · Clarify

B · Approach

C · Complexity

D · Edges

E · Code

F · Tradeoff

G · Score

Phase A — Clarify

Ask questions about input bounds, types, and edge constraints.

Ask the coach clarifying questions about the problem.

When you've covered this phase, advance to the next.