Maximum sum window of size k

Question

Given a series of per-minute PnL values and a window length k, find the best total PnL over any k consecutive minutes.

pnl = [1, -2, 3, 4, -1, 2], k = 3
-> 6            # window [3, 4, -1]

Return the maximum sum over all windows of exactly k consecutive elements. Aim for $O(n)$ , recomputing each window from scratch is $O(nk)$ .

Accepted Answer

Adjacent windows overlap in all but two elements. Sliding the window one step right adds one new element and drops one old element, so the sum can be updated in O(1) instead of recomputed in O(k). Tracing the example with k = 3: window sums are 2, 5, 6, 5, so the answer is 6. Time O(n), space O(1). One production note worth volunteering: with floating-point data, thousands of incremental += x - y updates accumulate rounding error. For long-running streams, either recompute the window sum periodically or keep prices as scaled integers. Takeaway. When consecutive answers share almost all their …

Maximum sum window of size k

Your answer

More Coding questions