Implement max profit with K transactions (DP)
Overview
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[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).