732. Two Trades Max
A pop-up kiosk sells festival wristbands and the list prices gives the resale price of one wristband on each day of the season. The owner may carry out at most two complete deals, where a deal means buying one wristband on some day and selling it on a later day. The second purchase may only happen after the first wristband has been sold (buying again on the day of a sale is fine), and no more than one wristband is ever held.
Return the largest total profit achievable with at most two deals, or 0 if every deal would lose money.
Aim for time O(n) and extra space O(1).
Example 1
- Input:
- prices = [6,2,8,3,9,1,5]
- Output:
- 12
- Explanation:
Buy at 2 and sell at 8 for 6, then buy at 3 and sell at 9 for 6, total 12; a single deal from 2 to 9 would give only 7.
Example 2
- Input:
- prices = [4,9,7,1,6]
- Output:
- 10
- Explanation:
Buy at 4 and sell at 9 for 5, then buy at 1 and sell at 6 for 5, total 10.
Example 3
- Input:
- prices = [10,8,6,5]
- Output:
- 0
- Explanation:
Prices only fall, so no deal earns anything and the answer is 0.
Constraints
1 ≤ prices.length ≤ 105
1 ≤ prices[i] ≤ 104
The answer fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)