473. Best Time to Buy and Sell Stock with Transaction Fee
You are given an array prices, where prices[i] is the price of one share of a stock on day i, and an integer fee — a commission that is charged once per completed transaction (a buy followed later by a sell).
You may trade as many times as you like, but you can hold at most one share at a time: you must sell the share you own before buying again. Buying and selling on the same day is pointless but allowed.
Return the maximum total profit you can end up with after any sequence of trades (possibly none).
Example 1:
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: Buy on day 0 at price 1 and sell on day 3 at price 8: profit 8 − 1 − 2 = 5. Then buy on day 4 at price 4 and sell on day 5 at price 9: profit 9 − 4 − 2 = 3. Total 5 + 3 = 8.
Example 2:
Input: prices = [1, 3, 7, 5, 10, 3], fee = 3
Output: 6
Explanation: With a fee of 3, splitting into two trades costs the commission twice. The single trade buy-at-1, sell-at-10 nets 10 − 1 − 3 = 6, which is the best possible.
Constraints:
- 1 ≤ prices.length ≤ 5 * 10⁴
- 1 ≤ prices[i] ≤ 5 * 10⁴
- 0 ≤ fee ≤ 5 * 10⁴
Hints:
At the end of any day you are in one of exactly two situations: you hold a share, or you don't. Track the best profit achievable for each situation.
Let cash = best profit while holding nothing and hold = best profit while holding one share. Each new price p offers two upgrades: cash = max(cash, hold + p − fee) and hold = max(hold, cash − p).
Charge the fee at exactly one end of the trade (say, at the sell). Counting it at both ends — or neither — double-counts or forgets the commission.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Expected output: 8