You know a commodity's price on each of n consecutive days. You may complete any number of trades, where a trade is buying one unit and later selling that same unit (you may hold at most one unit at a time, and must sell before buying again). Every completed sale costs a fixed transaction fee fee (paid out of the sale proceeds). Maximize total profit; if no trade is worthwhile, the answer is 0 (you are never forced to trade).
Line 1: two integers n fee.
Line 2: n space-separated positive integers, the prices on each day (empty if n = 0).
A single integer: the maximum total profit achievable.
Example 1
Input
6 1 5 2 9 1 7 3
Expected
11
Explanation
Buy at 2 and sell at 9 (net profit 6 after the fee), then buy at 1 and sell at 7 (net profit 5 after the fee): total profit 11.
Example 2
Input
3 5 10 10 10
Expected
0
Explanation
Prices never rise, so any trade would only lose money to the fee; the best choice is not to trade at all: profit 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 →