Best Time to Buy and Sell Stock with Transaction Fee
MediumDynamic Programming · Robinhood
prices[i] is the price of one share of a stock on day i. You may make as many trades as you like, where a trade is buying one share on some day and selling it on a later day. You can hold at most one share at a time, so you must sell before you buy again.
Every completed trade (one buy plus its sell) costs a flat fee. Return the maximum total profit you can make. If no trade is worth making, return 0.
Example 1
- Input:
- prices = [2, 7, 4, 10], fee = 2
- Output:
- 7
- Explanation
- One trade from 2 to 10 earns 10 - 2 - 2 = 6. Two trades (2 to 7, then 4 to 10) earn (7 - 2 - 2) + (10 - 4 - 2) = 3 + 4 = 7, which is better because the dip from 7 to 4 is bigger than the extra fee.
Example 2
- Input:
- prices = [2, 5, 4, 9], fee = 3
- Output:
- 4
- Explanation
- Two trades would earn (5 - 2 - 3) + (9 - 4 - 3) = 0 + 2 = 2, but a single trade from 2 to 9 earns 9 - 2 - 3 = 4. The dip from 5 to 4 is too small to pay for a second fee.
Example 3
- Input:
- prices = [9, 6, 5, 3], fee = 0
- Output:
- 0
- Explanation
- The price only falls, so every possible trade loses money and the best choice is not to trade.
Constraints
1 <= prices.length <= 5 * 10^41 <= prices[i] < 5 * 10^40 <= fee < 5 * 10^4