Stock Trading With at Most K Transactions
Mastery
prices[i] is a stock price on day i. You may complete at most k transactions (a buy followed by a sell), holding at most one share at a time. Return the maximum profit.
For k = 2 and prices = [3, 2, 6, 5, 0, 3] the answer is 7 (buy 2, sell 6, buy 0, sell 3).
The starter code tries every action on every day. It is correct but too slow for many days.
Examples
Example 1
Input:
max_profit_k(2, [3, 2, 6, 5, 0, 3])
Output:
7
Example 2
Input:
max_profit_k(1, [7, 6, 4, 3, 1])
Output:
0
Constraints
0 <= k <= 1000 <= len(prices) <= 40000 <= prices[i] <= 1000
Theory
Go to TheoryKeywords
dsa-sheetdynamic-programmingintervals-and-states
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.