Approach Summary
State machine: cash (not holding) and hold (holding). cash = max(cash, hold + price - fee); hold = max(hold, cash - price). Unlimited transactions.
How to Recognize This Pattern
- Unlimited transactions with per-trade fee
- State machine DP: two states, two transitions
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Array Dynamic Programming Greedy