Start learning free

LESSON 231 OF 410 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in Java: Brute Force, O(n * k)

Practice O(n * k) Read the full explanation

Given an input array of integers and a positive integer k, find the contiguous subarray of length exactly k with the maximum sum, and return its first and last indices.

Example

Input: nums = [5, 6, 1, 2, 6, 6, 4, 3], k = 3
Output: [4, 6]
Explanation: The subarray nums[4...6] has the maximum sum of 16
STEP 1 OF 8
    Ctrl + Enter to check

    JAVA · PARTIAL SUMS #1

    Maximum Sum Subarray Of Length K in Java, explained

    Problem overview

    The method maxSum receives an array of integers nums and a positive integer k. It looks at every contiguous block of exactly k elements (a "window"), finds the block with the largest sum, and returns the first and last index of that block as an int[] of two numbers.

    For nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3, the windows and their sums are:

    StartWindowSum
    05, 6, 112
    16, 1, 29
    21, 2, 69
    32, 6, 614
    46, 6, 416
    56, 4, 313

    The largest sum is 16, found in the window that starts at index 4 and ends at index 6, so the result is [4, 6]. The method reports positions, not the sum itself.

    Approach: try every window

    The most direct idea is to do exactly what the table does: for every possible start position, add up the k elements of that window, and remember the best sum seen so far together with the window's bounds.

    How many windows are there? A window of length k can start at index 0, 1, and so on up to nums.length - k, after which it would run past the end. That gives n - k + 1 windows, where n is the array length. Each window costs k additions, so the total is about (n - k + 1) * k operations, which is O(n * k).

    This is the brute-force solution, and it is a good first step because it is easy to get right. It repeats work, though: neighbouring windows share k - 1 elements, yet each sum is rebuilt from scratch. The sliding-window technique, covered in the other lesson on this problem, updates the sum by adding one element and removing one, bringing the time down to O(n). Understanding the brute force makes that improvement easy to see.

    Step by step

    1. Track the best sum. Declare maxSum and start it at Integer.MIN_VALUE, the smallest possible int. Whatever the first window's sum is, even a very negative one, it is at least that large and replaces it.
    2. Prepare the answer. answer starts as an empty int[]. It is never filled in place: each time a better window turns up, answer is pointed at a new two-element array.
    3. Loop over window starts. The index i runs from 0 up to and including nums.length - k. The condition is <= because the last window starts exactly at nums.length - k.
    4. Reset the window sum. Inside this loop, declare sum as 0. It lives inside the loop so each window begins from zero.
    5. Loop over the window. The index idx goes from i while it is less than i + k, which visits exactly k positions.
    6. Add each element nums[idx] to sum.
    7. Compare with the best. If sum is strictly greater than maxSum, store it in maxSum and set answer to {i, i + k - 1}. The strict comparison means that when two windows tie, the earlier one is kept.
    8. Return answer after both loops finish.

    The solution in Java

    class Solution {
    public int[] maxSum(int[] nums, int k) {
        int maxSum = Integer.MIN_VALUE;
        int[] answer = new int[]{};
        for (int i = 0; i <= nums.length - k; i++) {
            int sum = 0;
            for (int idx = i; idx < i + k; idx++) {
                sum += nums[idx];
            }
            if (sum > maxSum) {
                maxSum = sum;
                answer = new int[]{i, i + k - 1};
            }
        }
        return answer;
    }
}

    The Java details worth knowing:

    • A local variable named like the method. The method is maxSum and the local variable inside it is also maxSum. Java keeps method names and variable names apart, so this compiles, but a different name would be easier to read in code of your own.
    • Arrays are created with a size or with values. new int[]{} is an array of length 0, and new int[]{i, i + k - 1} is an array of length 2 holding those two values. Array lengths are fixed, which is why the answer is replaced rather than extended.
    • nums.length is a field, without parentheses. Writing nums.length() is a compile error. That differs from String.length() and List.size().
    • int sums can overflow. Adding many large values can pass 2,147,483,647 and wrap around to a negative number without any error. For arrays with big values, declare sum and maxSum as long.

    Complexity

    Time: O(n * k). The outer loop runs n - k + 1 times and the inner loop runs k times per window. When k is small this is close to linear, and when k is around n / 2 it grows like n². The sliding window brings it to O(n).

    Space: O(1). The method keeps a few integers and a two-element array, regardless of the input size.

    Edge cases and common mistakes

    • k equals the array length. There is exactly one window, and the loop runs once with i = 0. For [1, 2, 3] and k = 3, the result is [0, 2].
    • k is 1. Every window is one element, so the answer is the first position of the largest element, written twice: [1, 1] for [4, 9, 7], and [0, 0] for [4].
    • All negative numbers. [-3, -1, -2] with k = 2 returns [1, 2] (sum -3, better than -4). This is why maxSum starts at Integer.MIN_VALUE and not at 0: with 0, no negative sum would ever win, and answer would stay empty.
    • Ties. For [3, 3, 3, 3] and k = 2 every window sums to 6, and the answer is [0, 1], the earliest. Changing > to >= would return the last one instead.
    • k larger than the array. The loop condition i <= nums.length - k is false at once, so the method returns the empty array. It does not crash.
    • Off-by-one in the loop bound. Using i < nums.length - k skips the last window. Using i < nums.length makes the inner loop read past the end and throw ArrayIndexOutOfBoundsException.
    • Returning the sum. The expected result is the pair of indices, not the value 16.

    Testing

    • [5, 6, 1, 2, 6, 6, 4, 3] with k = 3 gives [4, 6].
    • [1, 2, 3] with k = 3 gives [0, 2].
    • [-3, -1, -2] with k = 2 gives [1, 2].
    • [4] with k = 1 gives [0, 0].
    • [3, 3, 3, 3] with k = 2 gives [0, 1].
    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free