Unify Stock-Trading Profit Variants
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
# Unify Stock-Trading Profit Variants
Given daily stock prices, return the maximum profit when you may complete at most `max_transactions` buy-then-sell transactions. Use `-1` to mean an unlimited number of transactions. Every completed sale pays a nonnegative transaction fee.
This single interface must cover the one-transaction, unlimited-transaction, and unlimited-with-fee variants.
### Function Signature
```python
def max_stock_profit(
prices: list[int],
max_transactions: int,
fee: int,
) -> int:
...
```
### Examples
```text
Input: prices = [7, 1, 5, 3, 6, 4], max_transactions = 1, fee = 0
Output: 5
Input: prices = [7, 1, 5, 3, 6, 4], max_transactions = -1, fee = 0
Output: 7
Input: prices = [1, 3, 2, 8, 4, 9], max_transactions = -1, fee = 2
Output: 8
```
### Constraints
- `0 <= len(prices) <= 200_000`
- `0 <= prices[i] <= 10^9`
- `max_transactions == -1` or `0 <= max_transactions <= len(prices)`
- `0 <= fee <= 10^9`
### Clarifications
- You may hold at most one share at a time.
- A transaction is completed by one buy followed later by one sell.
- At most one action may occur on a given day.
- Charge `fee` exactly once, when a share is sold.
- You may choose to make no transactions, so the result is never negative.
- Return `0` for an empty price list or when `max_transactions == 0`.
- Do not mutate `prices`.
### Hints
- Identify when a finite transaction cap can no longer constrain the answer.
- Model the best cash and holding states after each price.
- For a genuinely small finite cap, add the number of completed sales to the state.
Quick Answer: Implement one stock-profit interface for limited transactions, unlimited transactions, and per-sale fees. Model cash and holding states, handle zero or negative-value edge cases, and optimize the finite-cap dynamic program when the transaction limit cannot bind.
Return the maximum profit with at most a given number of buy-then-sell transactions, or unlimited transactions when the cap is -1. At most one share may be held, one action may occur per day, and every sale pays the fee.
Constraints
- Prices and fee are nonnegative integers.
- max_transactions is -1 or between zero and the number of days.
- At most one share may be held.
- The answer is never negative.
Examples
Input: {'prices':[7,1,5,3,6,4],'max_transactions':1,'fee':0}
Expected Output: 5
Explanation: One transaction buys at one and sells at six.
Input: {'prices':[7,1,5,3,6,4],'max_transactions':-1,'fee':0}
Expected Output: 7
Explanation: Unlimited trading captures two rises.
Hints
- When the cap is at least half the day count, it cannot bind.
- For a finite cap, index cash and hold states by completed sales.
- Use previous-day states for both buy and sell transitions.