Dynamic Programming - Best Time to Buy and Sell Stock with Transaction Fee

Given prices[] and a transaction fee, find the maximum profit from unlimited transactions (each transaction costs fee). You must sell before you buy again.

Input: prices=[1,3,2,8,4,9], fee=2 → Output: 8

Input: prices=[1,3,7,5,10,3], fee=3 → Output: 6

Two states: hold (holding stock) and cash (not holding). Transition: cash = max(cash, hold + price - fee); hold = max(hold, cash - price).

Initialize cash=0, hold=-prices[0].
For each price: new_cash = max(cash, hold + price - fee); new_hold = max(hold, cash - price).
Return cash.

class Solution { public int maxProfit(int[] prices, int fee) { int cash = 0, hold = -prices[0]; for (int price : prices) { int newCash = Math.max(cash, hold + price - fee); hold = Math.max(hold, cash - price); cash = newCash; } return cash; } }

Time Complexity: O(N)
Space Complexity: O(1)