Implement max profit with K transactions (DP)
Company: Citadel
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an array prices[0..n-1] of daily stock prices and an integer k, implement a bottom-up dynamic program to compute the maximum achievable profit with at most k buy-sell transactions (no overlapping positions). Requirements: (1) Return both the profit and the list of (buy_day, sell_day) pairs achieving it; break ties by lexicographically smallest sequence of pairs. (2) Time: O(nk), Space: O(k). (3) Handle edge cases k = 0, n < 2, and prices with plateaus. (4) Prove correctness via optimal substructure and explain how you avoid O(n^2 k).
Quick Answer: This question evaluates dynamic programming, algorithmic optimization, and complexity-analysis skills by requiring a bottom-up DP implementation that maximizes stock trading profit with at most k transactions while returning optimal buy-sell pairs under tie-breaking constraints.
Given an array prices where prices[i] is the stock price on day i and an integer k, write solution(prices, k) that returns a tuple (max_profit, transactions). transactions must be a list of at most k pairs (buy_day, sell_day), using 0-based day indices, such that buy_day < sell_day and consecutive transactions are strictly disjoint: b1 < s1 < b2 < s2 < .... Among all ways to achieve the maximum profit, return the lexicographically smallest transaction list. Compare two lists left to right by pair; compare pairs by buy_day first, then sell_day; if one list is a prefix of the other, the shorter list is smaller. Handle edge cases such as k = 0, n < 2, and plateaus in prices. Target a bottom-up dynamic program with O(nk) time and rolling O(k) numeric DP state; in the interview, be ready to justify optimal substructure and explain why maintaining the best buy balance avoids the naive O(n^2 k) scan over all earlier buy days.
Constraints
- 0 <= len(prices) <= 10000
- 0 <= k <= 100
- 0 <= prices[i] <= 10^9
- Transactions must satisfy buy_day < sell_day, and different transactions must be strictly disjoint in time.
Examples
Input: ([3, 2, 6, 5, 0, 3], 2)
Expected Output: (7, [(1, 2), (4, 5)])
Explanation: Buy on day 1 and sell on day 2 for profit 4, then buy on day 4 and sell on day 5 for profit 3. Total profit is 7.
Input: ([1, 3, 2, 0, 2], 2)
Expected Output: (4, [(0, 1), (3, 4)])
Explanation: The best two disjoint transactions are (0,1) for profit 2 and (3,4) for profit 2, totaling 4.
Hints
- Use exact-transaction DP states: cash[t] for the best profit after exactly t completed transactions and no stock in hand, and hold[t] for the best balance after opening transaction t.
- The O(n^2 k) version tries every earlier buy day for every sell day. You can avoid that by carrying forward the best value of cash[t-1] - prices[i] as you sweep from left to right.