hardDynamic Programming 1DPure DSA~35 min
Max Profit With Two Trades
A trading bot may open and close a position at most twice over a price series, never holding two positions at once. Given daily prices, maximize total profit across the (up to) two trades.
Problem
Given an array prices where prices[i] is the price on day i, return the maximum profit from at most two non-overlapping buy/sell transactions. You must sell before buying again.
Input
An array prices of n integers (1 ≤ n ≤ 10^5, 0 ≤ price ≤ 10^5).
Output
An integer: the maximum achievable profit.
Constraints
- At most two transactions
- No simultaneous positions (sell before re-buying)
- Profit is 0 if no profitable trade exists
Examples
Example 1
Input
prices = [3,3,5,0,0,3,1,4]
Output
6
Buy at 0 sell at 3 (+3), buy at 1 sell at 4 (+3) totals 6.
Example 2
Input
prices = [7,6,4,3,1]
Output
0
Prices only fall, so no trade is profitable.