Maximize profit with bounded sell window
MicrosoftSoftware Engineer · OnsiteLast updated
This question evaluates proficiency in array algorithms, time and space complexity analysis, and techniques for bounded-range optimization and streaming adaptation.
Given an array prices[0..n-1] of daily stock prices and an integer D ≥ 1, you may perform at most one transaction (buy then sell). The sell day j must satisfy i < j ≤ min(i + D, n −
- for the chosen buy day i. Return the maximum profit and the pair (i, j) achieving it; if no positive profit exists, return 0 and indicate that no transaction should be made. Design an O(n) time, O(
- extra space algorithm, and discuss how you would adapt it for streaming input and for very large D.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.