0715MediumArrayDynamic ProgrammingSliding Window

Two Separate Stretches Of The Output Log

Tracked in this browser only

Trains the technique from

LeetCode 1031Maximum Sum of Two Non-Overlapping Subarrays

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(n) for a log of n days: one pass to build the running totals and two linear sweeps.Space O(n) for the running totals.

Build running totals of the log so the output of any stretch is a subtraction. Then fix which of the two lengths lies to the left and sweep the right-hand stretch across the log, carrying with the sweep the best left-hand stretch of the other length that finishes before the right-hand stretch begins; that best-so-far is updated with exactly the one stretch that becomes eligible as the sweep advances a day, so every pair of positions is priced without being visited. Because either length may come first, the same sweep is run twice with the two lengths exchanged, and the larger of the two results is the answer.

Pythonentry point: best_two_stretches

def best_two_stretches(counts, firstSpan, secondSpan):
    # Running totals make any stretch's output an O(1) lookup.  For a fixed order of
    # the two lengths, sweep the right-hand stretch forward and carry the best
    # left-hand stretch that ends before it starts, so each right-hand position is
    # priced once.  Run the sweep twice, once for each order of the two lengths.
    # Time O(n) for a log of n days; space O(n) for the running totals.
    n = len(counts)
    running = [0] * (n + 1)
    for i, value in enumerate(counts):
        running[i + 1] = running[i] + value

    def sweep(left_len, right_len):
        best_left = 0
        best_total = 0
        for end in range(left_len + right_len, n + 1):
            split = end - right_len
            left = running[split] - running[split - left_len]
            if left > best_left:
                best_left = left
            total = best_left + running[end] - running[split]
            if total > best_total:
                best_total = total
        return best_total

    return max(sweep(firstSpan, secondSpan), sweep(secondSpan, firstSpan))

The obvious version

Try every start day for a stretch of each length, keep the pairs that share no day, add the two stretch outputs up by summing the days directly, and report the largest total. Quadratic in the length of the log with a further factor for the summing, but it makes no assumption about which stretch comes first.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_best_two_stretches(counts, firstSpan, secondSpan):
    n = len(counts)
    best = 0
    for i in range(n - firstSpan + 1):
        first = sum(counts[i:i + firstSpan])
        for j in range(n - secondSpan + 1):
            if i + firstSpan <= j or j + secondSpan <= i:
                total = first + sum(counts[j:j + secondSpan])
                if total > best:
                    best = total
    return best

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in