469. Trading With a Cap of k
Prices are given for n consecutive days. You may buy and sell at most k times, and
you must sell before buying again, so the trades never overlap. Print the largest total
profit, which is 0 if no trade helps.
prices 3 2 6 5 0 3, k = 2 -> 7 buy at 2 sell at 6, buy at 0 sell at 3
prices 5 4 3 2 1, k = 3 -> 0 every trade loses, so make none
Problem #406 is this with k = 1 and problem #444 is k = 2, both solved by naming
the states explicitly. With k a parameter the same idea has to be indexed by how many
trades remain, which is the step from two hand-written variables to an array.
## The states
free[t] best cash after completing at most t trades, holding nothing
hold[t] best cash while inside the t-th trade, holding one unit
hold is a cash figure and so is negative early on: buying at price v from
free[t-1] leaves free[t-1] - v.
For each price v:
hold[t] = max( hold[t], free[t-1] - v ) open trade t by buying today
free[t] = max( free[t], hold[t] + v ) close trade t by selling today
A trade is counted when it is OPENED, which is why hold[t] reads free[t-1] and
free[t] reads hold[t]. Counting on the sell instead also works but the indices
shift, and mixing the two conventions is the usual way this goes wrong.
## The loop order, which is the part that bites
Iterate t from k DOWN to 1.
Going upward lets free[t] be updated by today's price and then read by hold[t+1] in
the same iteration, which permits buying and selling on the same day and buying again
immediately. That does not fail loudly. It returns a larger number, and on a rising
series it returns the sum of all the daily gains no matter how small k is. The test
1 2 3 4 5 with k = 1 answers 4, and the upward order answers 4 as well, so it
passes. The test 6 1 3 2 4 7 with k = 2 answers 7 and separates them.
Updating hold[t] before free[t] within one t is deliberate and safe: buying and
selling the same unit on the same day contributes -v + v = 0, which never improves
anything.
## Cash bounds
Prices reach 10^9, so cash figures need 64 bits. The answer is at least 0, because
making no trade at all is always allowed.
Constraints - `1 ≤ n ≤ 20000` - `1 ≤ k ≤ 100` - `0 ≤ price ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n space-separated prices, in day order.
Output
Print the largest total profit achievable with at most k non-overlapping trades.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.