Best Time Buy/Sell Stock III — At Most 2 Transactions
Sanjeev SharmaAdvertisement
Problem
At most 2 buy-sell transactions. Maximize profit.
Approach — State Machine DP
States: buy1 (max negative price after first buy), sell1, buy2, sell2.
Time: O(n) | Space: O(1)
Solutions
Python
class Solution:
def maxProfit(self, prices: list[int]) -> int:
buy1=buy2=float('-inf'); sell1=sell2=0
for p in prices:
buy1=max(buy1,-p)
sell1=max(sell1,buy1+p)
buy2=max(buy2,sell1-p)
sell2=max(sell2,buy2+p)
return sell2
C++
class Solution {
public:
int maxProfit(vector<int>& p){
int buy1=INT_MIN,sell1=0,buy2=INT_MIN,sell2=0;
for(int x:p){
buy1=max(buy1,-x); sell1=max(sell1,buy1+x);
buy2=max(buy2,sell1-x); sell2=max(sell2,buy2+x);
}
return sell2;
}
};
Complexity
- Time: O(n) | Space: O(1)
Advertisement
