Best Time to Buy and Sell Stock III

The key idea

Track four running best-values as you sweep the prices once: the most you can hold after the first buy, after the first sell, after the second buy, and after the second sell. Each day updates these in order so the second transaction is allowed to build on the profit already banked by the first.

Problem

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 (you must sell the stock before you buy again).

Constraints

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

Examples

Input: prices = [3,3,5,0,0,3,1,4] Output: 6

Input: prices = [1,2,3,4,5] Output: 4

Input: prices = [7,6,4,3,1] Output: 0

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →