Lesson 49

The Variable-Sized Sliding Window Pattern (Maximum Sum Subarray)

The Variable-Sized Sliding Window Pattern

Some problems ask you to look at every possible piece of an array and combine their answers into one final result. The variable-sized sliding window is a clever trick that often lets you find that result without actually checking every piece. This makes a slow solution fast.

Let's first make sure we share the same words.

An array is just a row of numbers, like 3, 1, -6, 8, -2, 7. Each number sits at a position called an index (starting from 0).
A subarray is any unbroken stretch of that row. For example 8, -2, 7 is a subarray, and so is just 1 by itself. The numbers must be next to each other — you cannot skip any.

The problem we will solve

> Given an integer array arr, find the subarray with the largest sum, and return that sum.

We will work with this exact array throughout:

index:   0   1   2   3   4   5
value:   3   1  -6   8  -2   7

The best answer here is 13, coming from the subarray 8, -2, 7 (because 8 + (-2) + 7 = 13). Our job is to discover that 13 automatically.

When does this pattern apply?

A problem fits this pattern if it matches a simple template:

> Given an array, compute some value (call it function f) for all subarrays. Then apply another function (call it g) on those results and return the answer.

For our problem:

f is the sum of a subarray.
g is the maximum of all those sums.

One more requirement: you must be able to add or remove the effect of a single element from the running result of f. Sums allow this easily — you just add or subtract a number. This "add/remove" ability is what lets the window grow and shrink smoothly.

First attempt: the brute-force solution

The most obvious idea is to try every subarray, add up each one, and remember the biggest sum. We do this with two nested loops:

int maxSubarraySum(vector<int> &arr) {
    // Initialize maxSum to a very small number
    int maxSum = -1e9;
    // Use nested loops to calculate the sum of all subarrays
    for(int i = 0; i < arr.size(); i++) {
        int sum = 0;
        for(int j = i; j < arr.size(); j++) {
            sum += arr[j];
            // Update maxSum if the current sum is greater
            maxSum = max(sum, maxSum);
        }
    }
    return maxSum;
}

How it works in plain words:

The outer loop picks a starting point i.
The inner loop walks forward with j, adding each new number to sum. So sum is the total of the subarray from i to j.
Every time sum beats the best total we have seen, we update maxSum.

If you trace this on our array, the running totals climb and fall, and eventually the stretch 8, -2, 7 produces 13, which becomes the final maxSum.

This works correctly. But because of the two nested loops, it checks roughly N × N subarrays. Its time cost is O(N²) — if the array doubles in size, the work goes up four times. We can do better.

The key insight

Here is the observation that saves us: we do not need the sum of every subarray.

Think about building up a sum from left to right. As long as the running sum stays positive (or zero), keeping the earlier numbers can only help a later, bigger subarray — they add value. But the moment the running sum drops below zero, those earlier numbers are now a burden. Any future subarray would be better off throwing them away and starting fresh.

So instead of restarting from every index, we keep a single window that grows when things are going well and resets when the sum turns negative.

The variable-sized sliding window solution

We use two pointers, start and end, that mark the left and right edges of our current window. We also keep sum (the total inside the window) and maxSum (the best total seen so far).

The rules in each step:

Add the number at end to sum (this expands the window to the right).
If sum is bigger than maxSum, update maxSum.
If sum ever becomes negative, the window is no longer helping. Set start = end + 1 and reset sum = 0. This contracts the window back to size zero, ready to start fresh after the bad stretch.
Move end forward and repeat until we reach the end of the array.

Let's trace it on 3, 1, -6, 8, -2, 7:

Start with sum = 0, maxSum = 0.
Add 3 → sum = 3. Bigger than maxSum → maxSum = 3.
Add 1 → sum = 4. Bigger → maxSum = 4.
Add -6 → sum = -2. Negative! Reset: move start past this point, sum = 0.
Add 8 → sum = 8. Bigger → maxSum = 8.
Add -2 → sum = 6. Still positive, but not bigger than 8, so keep going.
Add 7 → sum = 13. Bigger → maxSum = 13.

The final answer is 13, found in a single pass.

Here is the linear-time implementation:

class Solution {
public:
    int maxSubarraySum(vector<int> &arr) {
        int n = arr.size();
        if (n == 0) {
            return 0;
        }
        // Initialize start and end to 0
        int start = 0;
        int end = 0;
        // Initialize sum to a default value (current sum)
        int sum = arr[end];
        // To store the maximum subarray sum found so far
        int maxSum = arr[end];
        // ... expand end across the array, reset when sum turns negative ...
    }
};

Because we only walk through the array once, this runs in O(N) time — far faster than the O(N²) brute force.

Why is it safe to skip subarrays?

It feels risky to throw subarrays away. How do we know we won't miss the real best answer? The proof rests on one promise we keep (an invariant):

> For the current window, the sum from start up to any point inside the window is never negative.

Now suppose adding the element at end makes the window sum sum(start, end) turn negative. We can then safely ignore two whole groups of subarrays:

Subarrays that start at start and stretch past end. Since sum(start, end) is negative, dropping that negative front part always gives a bigger total. So a subarray starting at end + 1 beats it — the one starting at start can never be the maximum.

Subarrays that start somewhere between start + 1 and end. Because our invariant says the part before them was non-negative, the piece they include up to end must itself be negative. So they too can never win against a fresh start after end.

That leaves only the subarrays worth checking:

Those starting at start and ending before end (we already considered these as the window grew).
Those starting after end (we handle these by resetting and moving on).

The algorithm does exactly this: it starts with an empty window where the promise trivially holds, expands while the promise stays true, and resets the moment it breaks. Because the promise is always maintained and we check the window sum at every step, we are guaranteed to find the true maximum — while only skipping subarrays that could never have been the answer.

The Variable-Sized Sliding Window Pattern (Maximum Sum Subarray)