Implement max profit with K transactions (DP)

Q: Implement max profit with K transactions (DP)

This is a Coding & Algorithms interview question from Citadel for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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).

Implement max profit with K transactions (DP)

Comments (0)