Two non-overlapping windows of fixed length

Question

You have a series of daily desk revenues. Choose two non-overlapping contiguous windows, one of length L and one of length M, to maximize their combined sum. The L window may come before or after the M window.

rev = [0, 6, 5, 2, 2, 5, 1, 9, 4], L = 1, M = 2
-> 20          # length-2 window [6, 5] = 11, length-1 window [9] = 9

Return the maximum combined sum in $O(n)$ .

Accepted Answer

Build a prefix-sum array so any window sum is a subtraction. Then handle the two orderings separately with a helper: "first window has length a, second window has length b, and the second ends at index i." As i sweeps right, maintain besta, the best length-a window sitting entirely to the left of the second window, and combine it with the current length-b window. Tracing the example: with the length-1 window first and length-2 window second, the sweep finds [6,5]=11 paired with the earlier [9]... but the strongest pairing overall is [6,5]=11 as the length-2 window plus [9]=9 as the length-1 w…

Two non-overlapping windows of fixed length

Your answer

More Coding questions