Maximum profit by buying and selling a share at most twice

Hard

Problem

prices[i] is a stock's price on day i. You may complete at most two transactions (buy then sell), and you must sell before you buy again. Return the maximum total profit.

Example 1

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

Buy at 0 and sell at 3 (+3), then buy at 1 and sell at 4 (+3).

Also asked as: Maximum profit by buying and selling a share atmost twice

Test cases

Case 1

Input:    [3,3,5,0,0,3,1,4]
Expected: 6

Case 2

Input:    [1,2,3,4,5]
Expected: 4

Case 3

Input:    [7,6,4,3,1]
Expected: 0

Case 4

Input:    [5]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Four running states

Time O(n)Space O(1)

Track best value after buy1, sell1, buy2, sell2 as you scan prices once.

function maxProfitTwice(prices) {
let buy1 = -Infinity, sell1 = 0, buy2 = -Infinity, sell2 = 0;
for (const p of prices) {
buy1 = Math.max(buy1, -p);
sell1 = Math.max(sell1, buy1 + p);
buy2 = Math.max(buy2, sell1 - p);
sell2 = Math.max(sell2, buy2 + p);
}
return sell2;
}