Best Time to Buy and Sell Stock III
Hard · Dynamic Programming · Array · Dynamic Programming
Problem
You are given prices, where prices[i] is the price of a stock on day i.
You may complete at most two transactions, where a transaction is one buy followed later by one sell. You cannot hold more than one share at a time, so you must sell before you buy again (selling and buying again on the same day is allowed).
Return the maximum profit you can achieve, or 0 if no trade makes money.
Examples
Input: prices = [2,5,1,4,8,3,6] Output: 10
Buy at 2 and sell at 5 (+3), then buy at 1 and sell at 8 (+7).
Input: prices = [9,7,4,1] Output: 0
The price only falls, so the best choice is not to trade.
Input: prices = [1,2,3,4,5] Output: 4
One trade from 1 to 5. Splitting it into two trades cannot earn more.
Constraints
- 1 <= len(prices) <= 10^5
- 0 <= prices[i] <= 10^5
Approaches
- Baseline: try every split day — time O(n²), space O(1)
Follow-up
Generalize to at most k transactions: keep buy[j] and sell[j] for j = 1..k, O(n·k) time. When k >= n / 2 the cap no longer binds and the answer is the sum of every rise.
Related problems
Start free on Cariara · Coding problems · System design studio
