Maximum Profit in Stock Trading with Transaction Fee

Problem

Given an array prices and a transaction fee, find the maximum profit from as many transactions as you like, where each transaction incurs the fee once.

Example

prices = [1,3,2,8,4,9], fee = 2
Output: 8
-- buy@1 sell@8 (profit 5), buy@4 sell@9 (profit 3) → total 8

Constraints

• 1 ≤ prices.length ≤ 5 × 10^4
• 1 ≤ prices[i] < 5 × 10^4
• 0 ≤ fee < 5 × 10^4

Approach

Greedy with two states: hold (max profit holding stock) and free (max profit not holding).

Follow-up

Combine with a cooldown constraint: you must wait one day after selling before buying again.