Citadel·Data Scientist·Technical Phone Screen
- Given an array of daily stock prices and an integer k, implement a bottom-up dynamic programming solution to find the maximum profit from at most k buy-sell transactions with no overlapping positions. Return both the profit and the actual list of buy/sell day pairs, breaking ties by lexicographically smallest sequence. Achieve O(nk) time and O(k) space, and handle edge cases like k=0, fewer than 2 prices, and plateau prices. Also prove correctness using optimal substructure and explain how you avoid the naive O(n^2 k) approach.
“This wrecked me a little.”