Best Time to Buy and Sell Stock III
At most two transactions — track four running states (after each buy/sell).
3 min read
dp state-machine
Problem#
At most two non-overlapping buy/sell transactions. Maximize profit.
Examples#
[3,3,5,0,0,3,1,4]→6[1,2,3,4,5]→4
Constraints#
1 <= n <= 10^5.
Approach#
Four running scalars: profit after the 1st buy, 1st sell, 2nd buy, 2nd sell. Each updates from the previous: b1 = max(b1, -price); s1 = max(s1, b1 + price); b2 = max(b2, s1 - price); s2 = max(s2, b2 + price).
Solution#
class Solution {public: int maxProfit(vector<int>& prices) { int b1 = INT_MIN, s1 = 0, b2 = INT_MIN, s2 = 0; for (int p : prices) { b1 = max(b1, -p); s1 = max(s1, b1 + p); b2 = max(b2, s1 - p); s2 = max(s2, b2 + p); } return s2; }};func maxProfit(prices []int) int { b1, s1, b2, s2 := math.MinInt32, 0, math.MinInt32, 0 for _, p := range prices { if -p > b1 { b1 = -p } if b1+p > s1 { s1 = b1 + p } if s1-p > b2 { b2 = s1 - p } if b2+p > s2 { s2 = b2 + p } } return s2}from typing import List
class Solution: def maxProfit(self, prices: List[int]) -> int: b1, s1, b2, s2 = float('-inf'), 0, float('-inf'), 0 for p in prices: b1 = max(b1, -p) s1 = max(s1, b1 + p) b2 = max(b2, s1 - p) s2 = max(s2, b2 + p) return s2var maxProfit = function(prices) { let b1 = -Infinity, s1 = 0, b2 = -Infinity, s2 = 0; for (const p of prices) { b1 = Math.max(b1, -p); s1 = Math.max(s1, b1 + p); b2 = Math.max(b2, s1 - p); s2 = Math.max(s2, b2 + p); } return s2;};class Solution { public int maxProfit(int[] prices) { int b1 = Integer.MIN_VALUE, s1 = 0, b2 = Integer.MIN_VALUE, s2 = 0; for (int p : prices) { b1 = Math.max(b1, -p); s1 = Math.max(s1, b1 + p); b2 = Math.max(b2, s1 - p); s2 = Math.max(s2, b2 + p); } return s2; }}function maxProfit(prices: number[]): number { let b1 = -Infinity, s1 = 0, b2 = -Infinity, s2 = 0; for (const p of prices) { b1 = Math.max(b1, -p); s1 = Math.max(s1, b1 + p); b2 = Math.max(b2, s1 - p); s2 = Math.max(s2, b2 + p); } return s2;}Editorial#
The state machine has 4 nodes (1st buy, 1st sell, 2nd buy, 2nd sell), each with two transitions (stay or take action). Updating in order ensures intra-day cascades don’t violate the “buy before sell” rule.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#