Intuition
Track two running bests each day: cash = most money with NO share in hand, hold = most money while holding one share. Selling pays the fee once. Roll both forward day by day; the answer is the final cash.
Explanation
Two states are enough
On any day you are in exactly one of two situations:
- cash — you hold no share; this is the max money you could have right now.
- hold — you hold exactly one share; this is your max money after having paid for that share.
Transitions
Moving from day i-1 to day i at price p:
cash = max(cash, hold + p - fee) # keep resting, or sell today (pay the fee)
hold = max(hold, cash - p) # keep holding, or buy today
We charge the fee on the sell side (you could equally charge it on buy — just be consistent). Crucially, use the freshly-updated cash when computing hold; buying today can reuse money you conceptually just had.
Initialization (day 0): cash = 0 (did nothing), hold = -prices[0] (bought the first share). The answer is the final cash — you never want to end holding a share.
Worked example
prices = [1, 3, 2, 8, 4, 9], fee = 2. Start cash = 0, hold = -1.
| day | price | cash = max(cash, hold+p-fee) | hold = max(hold, cash-p) |
|---|---|---|---|
| 1 | 3 | max(0, -1+3-2)=0 | max(-1, 0-3)=-1 |
| 2 | 2 | max(0, -1+2-2)=0 | max(-1, 0-2)=-1 |
| 3 | 8 | max(0, -1+8-2)=5 | max(-1, 5-8)=-1 |
| 4 | 4 | max(5, -1+4-2)=5 | max(-1, 5-4)=1 |
| 5 | 9 | max(5, 1+9-2)=8 | max(1, 8-9)=1 |
Final cash = 8. (Buy at 1, sell at 8 → 8-1-2 = 5; buy at 4, sell at 9 → 9-4-2 = 3; total 8.)
Complexity
- Time: O(n) — a single pass.
- Space: O(1) — two rolling scalars.
Implementation
class Solution {
public int maxProfit(int[] prices, int fee) {
// cash = max money holding no share; hold = max money holding one share.
int cash = 0, hold = -prices[0];
for (int i = 1; i < prices.length; i++) {
int p = prices[i];
cash = Math.max(cash, hold + p - fee);
hold = Math.max(hold, cash - p);
}
return cash;
}
}