Best Time to Buy and Sell Stock IV
Hard · Dynamic Programming · Array · Dynamic Programming
Problem
You are given a number k and a list prices, where prices[i] is the price of a stock on day i.
You may make at most k trades. A trade is one purchase followed by a later sale. You can hold at most one share at a time, so you must sell before you buy again.
Return the largest total profit you can make. Making no trade at all, for a profit of 0, is allowed.
Examples
Input: k = 1, prices = [3,8,2,10] Output: 8
With one trade, buy at 2 and sell at 10.
Input: k = 2, prices = [3,8,2,10] Output: 13
Buy at 3 and sell at 8 (+5), then buy at 2 and sell at 10 (+8).
Input: k = 2, prices = [1,4,2,7,3,9] Output: 12
The best two trades are 1 → 7 (+6, riding through the dip) and 3 → 9 (+6).
Constraints
- 1 <= k <= 100
- 1 <= len(prices) <= 1000
- 0 <= prices[i] <= 1000
Approaches
- Baseline: try every buy day for the last trade — time O(k · n²), space O(k · n)
Follow-up
With k large, the O(n · k) table is wasteful. The shortcut for 2k >= n handles the extreme; for k between, there is an O(n log n) method that pairs valleys and peaks with a stack and merges the cheapest-to-lose trades with a heap until only k remain.
Related problems
Start free on Cariara · Coding problems · System design studio
