A share has a known price on each of n days. You may complete as many buy-then-sell trades as you like, holding at most one share at a time. Each time you sell, you pay a fixed transaction fee. A trade's net gain is therefore (sell price) minus (buy price) minus fee.
Return the maximum total profit. Doing nothing yields a profit of 0.
Line 1: two integers n and fee.
Line 2: n space-separated non-negative integers, the daily prices (present whenever n >= 1).
A single integer: the maximum total net profit.
Example 1
Input
6 2 1 3 2 8 4 9
Expected
8
Explanation
Buy at 1, sell at 8 for net 8-1-2 = 5; buy at 4, sell at 9 for net 9-4-2 = 3. Total 8. Splitting differently cannot beat 8 once the fee is charged per sale.
Example 2
Input
4 5 4 5 6 7
Expected
0
Explanation
The whole rise is only 3, smaller than the fee of 5, so any trade loses money. The best is to do nothing, giving 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →