Show problems as
Classic problem #1031MediumArrayDynamic ProgrammingSliding Window

Maximum Sum of Two Non-Overlapping Subarrays

Real-world version: Two Separate Stretches Of The Output Log
Tracked in this browser only
Read Maximum Sum of Two Non-Overlapping Subarrays on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A turbine keeps a daily output log, where counts[i] is the output recorded on day i.

A report has to quote two stretches of the log. A stretch is a run of consecutive days. One stretch has to cover exactly firstSpan days and the other exactly secondSpan days, and the two stretches must not share a single day.

The two stretches may sit in either order along the log: the firstSpan stretch may start before the secondSpan stretch or after it.

Return the largest total output the two stretches can quote between them.

Examples

Example 1

Input
counts = [9, 0, 3, 3, 3, 0], firstSpan = 3, secondSpan = 1
Output
18

Quoting day 0 on its own as the one-day stretch gives 9, and days 2 to 4 as the three-day stretch give 3 + 3 + 3 = 9, so the two stretches quote 18 between them. They share no day, and the one-day stretch is allowed to sit first.

Example 2

Input
counts = [4, 1, 1, 6, 5], firstSpan = 1, secondSpan = 2
Output
15

The one-day stretch takes day 0 for 4 and the two-day stretch takes days 3 and 4 for 6 + 5 = 11, a total of 15 across two stretches that share no day.

Example 3

Input
counts = [7, 7, 7, 7, 7, 7], firstSpan = 3, secondSpan = 3
Output
42

Every day records 7 and the two three-day stretches have to cover six different days, so the total is 6 * 7 = 42 wherever they are placed.

Constraints

  • 1 <= firstSpan, secondSpan <= 1000
  • 2 <= firstSpan + secondSpan <= 1000
  • 2 <= counts.length <= 1000
  • The log is long enough to hold both stretches: firstSpan + secondSpan <= counts.length.
  • 0 <= counts[i] <= 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_two_stretches(counts: list[int], firstSpan: int, secondSpan: int) -> int:
Java
public int bestTwoStretches(int[] counts, int firstSpan, int secondSpan)

More on the same topics