You are given a list of integers prices where prices[i] is the price of a stock on day i, and an integer fee.
A transaction is buying one share on some day and selling it on a later day. Every transaction costs fee, so its profit is the selling price minus the buying price minus fee. You may complete any number of transactions. You can hold at most one share at a time, so you must sell the share you hold before you buy again.
Return the maximum total profit you can make.
Note that you are not required to trade at all.
Examples
Example 1
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: Buy on day 0 (price 1) and sell on day 3 (price 8) for a profit of 8 - 1 - 2 = 5. Then buy on day 4 (price 4) and sell on day 5 (price 9) for a profit of 9 - 4 - 2 = 3. The total profit is 5 + 3 = 8.
Example 2
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
Explanation: Buy on day 0 (price 1) and sell on day 4 (price 10) for a profit of 10 - 1 - 3 = 6. Two transactions (day 0 to day 2, then day 3 to day 4) would pay the fee twice and earn only (7 - 1 - 3) + (10 - 5 - 3) = 5.
Example 3
Input: prices = [9,7,4,2], fee = 1
Output: 0
Explanation: Prices only go down, so every transaction loses money. Making no transactions gives a profit of 0.
Constraints
1≤prices.length≤5⋅104
1≤prices[i]<5⋅104
0≤fee<5⋅104
Loading editor...
Run checks the sample cases; Submit runs every case.
Samples 3
Custom 0
passedwrong answertime limiterrorran, no expected valuenot run