Simple: unlimited transactions
Two states: hold or not.
int hold = -prices[0], sold = 0;
for (int i = 1; i < n; i++) {
int prevHold = hold, prevSold = sold;
hold = max(prevHold, prevSold - prices[i]);
sold = max(prevSold, prevHold + prices[i]);
}
return sold;Advertisement
With cooldown
Three states: hold, sold, cooldown. After selling, must wait one day.
Advertisement
With transaction fee
Two states, subtract fee on sell.
K transactions
dp[k][day][state]. Track number of transactions used. O(NK) time + space.