188. Best Time to Buy and Sell Stock IV
hardMaximize profit with at most k non-overlapping transactions. The general-k state machine — 2k+1 states or two parallel arrays of length k.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k. Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Constraints
1 <= k <= 1001 <= prices.length <= 10000 <= prices[i] <= 1000
Examples
Example 1
k = 2, prices = [2,4,1]2Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2
k = 2, prices = [3,2,6,5,0,3]7Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Generalize Stock III. Two arrays buy[1..k] and sell[1..k] tracking max profit after j-th buy or sell.
Hint 2
For each price update buy[j] = max(buy[j], sell[j-1] - p) and sell[j] = max(sell[j], buy[j] + p).
Hint 3
If k >= n/2 the constraint is non-binding — fall back to the unlimited-transactions greedy.
Solution approach
Reveal approach
Maintain two arrays buy and sell of length k+1 where buy[j] is the best profit when mid-jth transaction (just bought, haven't sold) and sell[j] is the best profit after completing j transactions. Initialize buy[j] = -infinity and sell[j] = 0 for all j. For each price p in prices and each j from 1 to k: buy[j] = max(buy[j], sell[j-1] - p); sell[j] = max(sell[j], buy[j] + p). Return sell[k]. O(n*k) time, O(k) space. Optimization: if k >= n/2 the cap is non-binding, so reduce to the greedy unlimited-transactions solution that sums every positive price diff — avoids O(n*n/2) blow-up on tiny n with huge k.
Complexity
- Time
- O(n * k)
- Space
- O(k)
Related patterns
- dynamic-programming
- state-machine
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Citadel
Practice these live with InterviewChamp.AI
Drill Best Time to Buy and Sell Stock IV and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →