733. K Trades Max
A bike-share operator can swap one battery pack at a time between charging hubs. Over a run of days, prices[i] is the price of a pack on day i, and the operator may perform at most k complete deals, where a deal is buying one pack on some day and selling it on a later day. A new pack can only be bought after the previous one was sold (buying again on the day of a sale is allowed).
Return the maximum total profit using at most k deals, or 0 if no deal helps. Note that k may be far larger than useful; the answer must still be computed quickly.
Aim for time O(n*k) (or O(n) when k is large) and space O(k).
Example 1
- Input:
- k = 2, prices = [3,7,2,8,1,9]
- Output:
- 14
- Explanation:
With two deals the best is buy 1 / sell 9 for 8 and buy 2 / sell 8 for 6, total 14.
Example 2
- Input:
- k = 3, prices = [5,1,6,2,7,3,8]
- Output:
- 15
- Explanation:
Three deals each gain 5 (1 to 6, 2 to 7, 3 to 8), total 15.
Example 3
- Input:
- k = 1, prices = [9,4,6,12,2]
- Output:
- 8
- Explanation:
A single deal can only be buy 4 / sell 12 for a profit of 8.
Constraints
0 ≤ k ≤ 109
1 ≤ prices.length ≤ 2 * 104
0 ≤ prices[i] ≤ 1000
The answer fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n*k)
- Space
- O(k)