443. Trading With a Fee
Prices are given for n consecutive days. You may buy and sell any number of
times but hold at most one unit at a time, and every COMPLETED trade costs a fixed
fee. Print the largest total profit, which is 0 if no trade is worth making.
1 3 2 8 4 9 with fee 2 -> 8
Without a fee, every rise is worth taking. With one, a rise smaller than the fee is worth skipping, and two adjacent small rises may be worth merging into one larger trade to pay the fee once. Deciding which is which greedily is the trap.
Two states suffice:
hold the best total so far while holding one unit
free the best total so far while holding nothing
hold = max(hold, free - price)
free = max(free, hold + price - fee)
Charging the fee on SELLING rather than on buying is a choice, and either works as long as it is consistent. Charging it on both is the error that halves plausible answers.
Compare problem 442, where the obstacle is a timing rule and needs three states. Here the obstacle is a cost and two suffice, because nothing about the past restricts what you may do next: only how much it is worth.
Both lines must read the values of the previous day. Writing hold first and then
using it for free allows buying and selling on the same day, which earns
-fee and quietly caps every answer.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ price ≤ 1000000` - `0 ≤ fee ≤ 1000000`
Input
The first line contains two integers n and fee.
The second line contains n space-separated prices.
Output
Print the largest total profit after fees, or 0 if no trade is worthwhile.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.