Skip to main content

188. Best Time to Buy and Sell Stock IV

hard

Maximize profit with at most k non-overlapping transactions. The general-k state machine — 2k+1 states or two parallel arrays of length k.

By Sam K., 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 <= 100
  • 1 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

Examples

Example 1

Input
k = 2, prices = [2,4,1]
Output
2

Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2

Input
k = 2, prices = [3,2,6,5,0,3]
Output
7

Explanation: 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.

Output

Press Run or Cmd+Enter to execute

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
  • Google
  • Citadel

More DP 1D practice problems

See all DP 1D problems →