Maximum Sum Subarray of Size K

Given an array and a number k, find the largest sum of any k consecutive elements. The brute-force solution recomputes each window from scratch; the sliding window reuses the previous sum and does two arithmetic operations per element instead of k.

This is the smallest problem in which the sliding-window pattern appears cleanly, which makes it the right place to understand the pattern rather than memorise it.

Written against Java 17.

The problem

Input:  nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9        the window [5, 1, 3]

Input:  nums = [2, 3, 4, 1, 5], k = 2
Output: 7        the window [3, 4]

Brute force

static int maxSumBruteForce(int[] nums, int k) {
    int best = Integer.MIN_VALUE;

    for (int start = 0; start + k <= nums.length; start++) {
        int sum = 0;
        for (int i = start; i < start + k; i++) {
            sum += nums[i];
        }
        best = Math.max(best, sum);
    }
    return best;
}

O(n·k). The waste is visible: consecutive windows overlap in k - 1 elements, and every one of them is added again.

start + k <= nums.length is the loop bound, not start < nums.length. Writing the latter walks off the end on the last few starts.

The sliding window

static int maxSum(int[] nums, int k) {
    if (nums.length < k) {
        throw new IllegalArgumentException("Array shorter than the window");
    }

    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];             // the first window
    }

    int best = windowSum;

    for (int end = k; end < nums.length; end++) {
        windowSum += nums[end] - nums[end - k];   // add entering, subtract leaving
        best = Math.max(best, windowSum);
    }
    return best;
}

O(n) time, O(1) space. Each element is added once and subtracted once.

The two indices

nums[end] is the element entering the window. nums[end - k] is the element leaving it. Getting the second wrong is the whole difficulty of the pattern.

With k = 3 and end = 3: the previous window was indices 0, 1, 2; the new one is 1, 2, 3. Index 3 enters, index 0 leaves, and end - k is 3 - 3 = 0. Correct.

end - k + 1 would subtract index 1, which is still inside the window, the sum then drifts and the answer is wrong by an amount that depends on the data, so a small test can easily pass.

The other boundary is the loop start. end begins at k, not at 0 or k - 1, because the first k elements were already summed in the priming loop. Starting at k - 1 adds one element twice.

Why best is initialised from the first window

int best = windowSum;                 // correct
int best = 0;                         // wrong for all-negative input
int best = Integer.MIN_VALUE;         // correct but unnecessary

Initialising to 0 returns 0 for [-5, -2, -8] with k = 2, which is not the sum of any window. The array may be entirely negative, and the answer is then the least negative window.

Seeding from the first real window avoids the sentinel entirely and makes the all-negative case work without a special path. That is generally the better move: start from an actual candidate rather than from a value chosen to lose every comparison.

Negative numbers otherwise need no handling. The add-and-subtract arithmetic is unaffected by sign, which is worth stating because the related “maximum subarray of any size” problem, Kadane’s algorithm, does need a sign-dependent decision.

Tracing it

nums = [2, 1, 5, 1, 3, 2], k = 3:

end	entering	leaving	windowSum	window	best
—	—	—	8	2 1 5	8
3	1	2	7	1 5 1	8
4	3	1	9	5 1 3	9
5	2	5	6	1 3 2	9

Six elements, six additions and three subtractions — against eighteen additions for the brute force.

Overflow

windowSum += nums[end] - nums[end - k];

With k elements near Integer.MAX_VALUE, the running sum overflows and wraps negative. The comparison then picks the wrong window, silently.

long windowSum = 0;
long best;

Worth doing whenever the input range is not bounded by the problem statement. k = 10⁵ and values up to 10⁴ reaches 10⁹, which is already most of an int.

Fixed window against variable window

This problem has a fixed window: k is given, so exactly one element enters and one leaves per step, and there is no shrink condition. The loop has no inner while.

The variable-size family — “the smallest window summing to at least target”, “the longest substring with at most k distinct characters”, longest substring with same letters after replacement — grows the right edge and shrinks the left edge conditionally:

int left = 0, sum = 0, best = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {                    // shrink while still valid
        best = Math.min(best, right - left + 1);
        sum -= nums[left++];
    }
}

The while is what distinguishes them, and it is still O(n): each index enters once and leaves at most once, so the inner loop runs at most n times in total across the whole outer loop. That amortised argument is the part worth understanding — the nested loop looks quadratic and is not.

Recognising which variant a problem is comes down to one question: is the window size given, or is it what you are solving for?

Returning the window, not just the sum

Most statements ask only for the sum. Returning the window itself needs one more variable and no extra passes:

record Window(int start, int end, long sum) { }

static Window maxWindow(int[] nums, int k) {
    long windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i];

    long best = windowSum;
    int bestStart = 0;

    for (int end = k; end < nums.length; end++) {
        windowSum += nums[end] - nums[end - k];
        if (windowSum > best) {
            best = windowSum;
            bestStart = end - k + 1;
        }
    }
    return new Window(bestStart, bestStart + k - 1, best);
}

end - k + 1 is the start of the current window — the same expression that was wrong as a subtraction index is right here, which is a good reason to compute it once into a named variable rather than inlining it twice with different meanings.

Note > rather than >= in the comparison: strict inequality keeps the first maximal window when several tie. Using >= keeps the last. Neither is more correct, and the problem statement rarely says — worth choosing deliberately so the output is at least deterministic.

Edge cases

• k equals the array length — one window; the priming loop does all the work and the second loop never runs.
• k greater than the length — no valid window. Throw, or return a documented sentinel; do not let the priming loop walk off the end.
• k of zero or negative — meaningless. Validate.
• A single element with k = 1 — works; the second loop does not run.

The k > length case is the one that produces an ArrayIndexOutOfBoundsException rather than a wrong answer, so it is at least loud.

More in the algorithms guides.

Frequently asked questions

What is the time complexity?

O(n) with O(1) space. Each element is added once and subtracted once, against O(n·k) for recomputing every window.

Which element is subtracted?

nums[end - k] — the one leaving the window. end - k + 1 is still inside it, and using it makes the running sum drift.

Where should the second loop start?

At end = k. The first k elements were summed in the priming loop; starting earlier adds one of them twice.

Why not initialise best to zero?

An all-negative array then returns 0, which is not the sum of any window. Seed best from the first computed window instead.

Do negative numbers need special handling?

No. The add-and-subtract arithmetic is sign-agnostic. Only the initialisation of best is affected.

Can the sum overflow?

Yes, with large values or a large k. Use long unless the problem bounds the input.

What if k is larger than the array?

There is no valid window. Validate and throw rather than letting the priming loop read past the end.

How is this different from Kadane’s algorithm?

Kadane finds the best subarray of any size and makes a sign-dependent decision at each step. Here the size is fixed, so the window slides mechanically.

When does the sliding window need an inner while loop?

When the window size is variable and there is a validity condition to restore. A fixed size never shrinks conditionally.

Is the variable-window version still O(n)?

Yes. Each index enters the window once and leaves at most once, so the inner loop runs at most n times in total — amortised, not per iteration.