Two Separate Windows

Medium

You are given an array of non-negative integers values and two lengths len_a and len_b. Pick two contiguous stretches of the array: one of length len_a and one of length len_b. They must not share any element, but they can come in either order; either one may be on the left. Return the largest possible combined sum of the two stretches.

Example 1

values=[2, 8, 1, 0, 4, 6, 3], len_a=2, len_b=1 → 18

The stretch [4, 6] of length 2 gives 10 and the stretch [8] of length 1 adds 8, for 18 in total.

Example 2

values=[5, 1, 1, 9, 9], len_a=1, len_b=3 → 24

The length-3 stretch may come first or second: [1, 9, 9] gives 19 and [5] before it adds 5, for 24.

Example 3

values=[4, 4], len_a=1, len_b=1 → 8

Constraints

1 ≤ len_a, len_b ≤ 1000
len_a + len_b ≤ len(values) ≤ 10⁵
0 ≤ values[i] ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Sliding Window

Similar problems

Evenly Stepped Stretches Medium Longest Run of Ones With One Fix Medium Longest Shared Run Medium Sawtooth Readings Medium Two Separate Segments With a Given Sum Medium

Input

values=[2, 8, 1, 0, 4, 6, 3], len_a=2, len_b=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 111 tests on the server, hidden ones included.