Limited Trade Budget
Problem
prices[i] is a share's price on day i. You may hold at most one share at a time, and your account allows at most k completed trades (a trade is one buy followed later by one sell).
Return the maximum total profit.
Example 1
- Input:
- k = 2, prices = [3, 2, 6, 5, 0, 3]
- Output:
- 7
Buy at 2, sell at 6 (+4); buy at 0, sell at 3 (+3).
Example 2
- Input:
- k = 2, prices = [2, 4, 1]
- Output:
- 2
Example 3
- Input:
- k = 0, prices = [1, 9]
- Output:
- 0
No trades allowed.
Constraints
- 0 ≤ k ≤ 100
- 1 ≤ prices.length ≤ 1000
- 0 ≤ prices[i] ≤ 1000
Hint
Show the first hint
The free/hold machine forgets how many trades you have made. Add that number to the state.
Walkthrough
How to approach it
01Clarify before coding
- Does a trade count when you buy or when you sell? Count it at the buy; a buy without a sell never helps anyway.
- Can k be larger than the number of useful trades? Yes; then the limit does not bind.
- Can I buy and sell on the same day? It earns nothing, so allowing it is harmless.
02Brute force
Recurse over (day, trades left, holding), trying wait / buy / sell. With memoisation this is the DP, with n·k·2 states.
Cost: Without memo: exponential. With memo: O(n·k) time and O(n·k) space, plus recursion depth n.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.