Maximum Sum Subarray of Size K: Fixed-Size Window, Add Right, Subtract Left

• Fixed-size sliding window – finds the maximum sum among all contiguous subarrays of length K.
• Slide operation – windowSum += a[right] - a[right - K] adds the new element and removes the old in one step.
• O(n) time, O(1) space – each slide is constant time; the whole scan visits each element once.
• Improvement – brute force recomputes each window from scratch in O(K), giving O(n * K) total.
• Guard – if K > array length, no valid window exists.

What is the Maximum Sum Subarray of Size K problem?

Given an array of integers and a positive integer K, find the maximum sum among all contiguous subarrays of exactly K elements. For example, in [2, 1, 5, 1, 3, 2] with K = 3, the maximum sum is 5 + 1 + 3 = 9.

At the National Bank of India, the marketing team wants to find each customer's best K-day deposit streak to time a loyalty offer.

How does the fixed-size sliding window work?

1. Compute the sum of the first K elements as the initial window sum.
2. Set this as the current best.
3. Slide the window one position at a time: add the element entering on the right, subtract the element leaving on the left.
4. Compare the updated sum against the best.

Array: [2, 1, 5, 1, 3, 2]   K = 3

Initial window: [2, 1, 5] = 8, best = 8
Slide right: +1 -2 = 7, best = 8
Slide right: +3 -1 = 9, best = 9
Slide right: +2 -5 = 6, best = 9

Answer: 9

How do you implement it? (with code)

package com.bank.analysis;

import java.math.BigDecimal;

public class MaxSumWindowK {

    public static BigDecimal maxSumOfSizeK(BigDecimal[] deposits, int k) {
        if (deposits == null || k <= 0 || k > deposits.length) {
            throw new IllegalArgumentException(
                "Invalid input: K must be between 1 and array length");
        }

        // Compute initial window sum
        BigDecimal windowSum = BigDecimal.ZERO;
        for (int i = 0; i < k; i++) {
            windowSum = windowSum.add(deposits[i]);
        }
        BigDecimal best = windowSum;

        // Slide the window
        for (int right = k; right < deposits.length; right++) {
            windowSum = windowSum.add(deposits[right])
                                 .subtract(deposits[right - k]);
            if (windowSum.compareTo(best) > 0) {
                best = windowSum;
            }
        }
        return best;
    }

    public static void main(String[] args) {
        BigDecimal[] deposits = {
            new BigDecimal("200"), new BigDecimal("100"),
            new BigDecimal("500"), new BigDecimal("100"),
            new BigDecimal("300"), new BigDecimal("200")
        };
        System.out.println("Max 3-day deposits: " + maxSumOfSizeK(deposits, 3));
    }
}

Max 3-day deposits: 900

Why is this better than brute force?

Brute force recomputes each window's sum from scratch, which costs O(K) additions per window and O(n * K) total. The sliding window reuses the previous sum, changing only two terms per slide, giving O(n). This reuse of overlapping work is the essence of the window technique.

| Approach | Time | Space |
|---|---|---|
| Brute force (recompute each window) | O(n * K) | O(1) |
| Fixed-size sliding window | O(n) | O(1) |

How is this different from Kadane's Algorithm?

| Aspect | Fixed-size window (size K) | Kadane's (any size) |
|---|---|---|
| Window width | Fixed at K | Variable (1 to n) |
| Slide rule | Add right, subtract left | Extend or reset |
| Negative values | No special handling | Reset when extending hurts |
| Use case | Best fixed-length streak | Best variable-length streak |

What are the edge cases?

• K equals array length – the only window is the entire array; return its sum.
• K equals 1 – the answer is the maximum element.
• K greater than array length – no valid window; throw or return sentinel.
• All negative values – the answer is the least negative K-length window.
• Overflow – use long or BigDecimal for the accumulator when values are large.

What about returning the starting index?

Track the index of the right edge when the best is updated. The starting index of the best window is bestRight - K + 1.

int bestStart = 0;
for (int right = k; right < n; right++) {
    windowSum = windowSum.add(deposits[right]).subtract(deposits[right - k]);
    if (windowSum.compareTo(best) > 0) {
        best = windowSum;
        bestStart = right - k + 1;
    }
}

What should a senior engineer know?

The fixed-size sliding window is the simplest member of the sliding window family. Variable-size windows (like minimum-size subarray sum) require a shrink step. This fixed version is also the building block for more complex window problems like sliding window maximum (using a deque).

What are common interview follow-up questions?

• What if K is not fixed? – Use Kadane's for maximum any-length, or variable window for constrained lengths.
• What about the minimum sum window? – Same technique, track minimum instead of maximum.
• Can you find the average instead? – Divide the window sum by K at each step.