‹ DS&A interview · Socratic
DSA · Dynamic Programming · #40

Best Time to Buy and Sell Stock IV

Module 47 · difficulty 4/5·⏱ 30:00starts on first keystroke

You are given an integer `k` and an array `prices` where `prices[i]` is the price of a given stock on day `i`. 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 (you must sell the stock before you buy again). Implement the function `maxProfit(k, prices)` that returns the maximum profit.

Examples
  • k = 2, prices = [2,4,1] → 2 — Buy on day 0 (price = 2) and sell on day 1 (price = 4), profit = 4 - 2 = 2.
  • k = 2, prices = [3,2,6,5,0,3] → 7 — Buy on day 1 (price = 2), sell on day 2 (price = 6), profit = 4. Then buy on day 4 (price = 0), sell on day 5 (price = 3), profit = 3. Total = 7.
  • k = 0, prices = [1,3] → 0 — No transactions allowed.
Constraints
  • · 0 <= k <= 100
  • · 0 <= prices.length <= 1000
  • · 0 <= prices[i] <= 1000
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.