Course4all
Join us on telegram
Home/dsa/Sliding Window/Maximum Sum Subarray of Size K

Maximum Sum Subarray of Size K

Master this topic with zero to advance depth.

Maximum Sum Subarray of Size K

Given an array of integers nums and a positive integer k, find the maximum sum of any contiguous subarray of size k.

Visual Representation

nums = [2, 1, 5, 1, 3, 2], k = 3 Step 1: [2, 1, 5], 1, 3, 2 (Sum = 8) Step 2: 2, [1, 5, 1], 3, 2 (Sum = 7) Step 3: 2, 1, [5, 1, 3], 2 (Sum = 9) -> MAX Step 4: 2, 1, 5, [1, 3, 2] (Sum = 6)
Easy

Examples

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

Subarray [5, 1, 3] has the maximum sum of 9.

Approach 1

Level I: Brute Force (Nested Loops)

Intuition

The most basic way to solve this is to check every possible contiguous subarray of size k and calculate its sum. We keep track of the maximum sum found so far.

Thought Process

  1. Iterate through every possible starting index i from 0 to n - k.
  2. For each i, start another loop to sum up the next k elements.
  3. Update maxSum if the current subarray sum is larger.

Pattern Identification

This is a Naive Search pattern. We are re-calculating the sum for overlapping parts of subarrays, which is the main bottleneck.

⏱ O(N * K)💾 O(1)

Detailed Dry Run

Outer Loop (i)Inner Loop (j)Current SumMax SumAction
00, 1, 22+1+5 = 88Init Max
11, 2, 31+5+1 = 78No Change
22, 3, 45+1+3 = 99Update Max
33, 4, 51+3+2 = 69No Change
java
public class Main {
    public static int findMaxSum(int[] nums, int k) {
        int maxSum = 0;
        int n = nums.length;
        // Iterate through all possible starting points
        for (int i = 0; i <= n - k; i++) {
            int currentSum = 0;
            // Sum k elements starting from i
            for (int j = i; j < i + k; j++) {
                currentSum += nums[j];
            }
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 5, 1, 3, 2};
        int k = 3;
        System.out.println("Max Sum: " + findMaxSum(nums, k)); // Expected: 9
    }
}
Approach 2

Level II: Prefix Sums (O(N) Space)

Intuition

We can precompute a prefix sum array where prefix[i] stores the sum of elements from 0 to i-1. The sum of any subarray nums[i...j] can then be calculated in O(1)O(1) as prefix[j+1] - prefix[i].

Thought Process

  1. Create an array prefix of size n + 1.
  2. Fill prefix such that prefix[i+1] = prefix[i] + nums[i].
  3. Iterate from i = 0 to n - k and calculate sum = prefix[i+k] - prefix[i].
  4. Update maxSum accordingly.

Pattern: Space-Time Tradeoff

This approach reduces the calculation time to O(1)O(1) per subarray but uses O(N)O(N) extra space.

⏱ O(N) - One pass for prefix sum, another for maximums.💾 O(N) - To store the prefix sum array.
java
public class Main {
    public static int findMaxSum(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
        
        int maxSum = 0;
        for (int i = 0; i <= n - k; i++) {
            maxSum = Math.max(maxSum, prefix[i + k] - prefix[i]);
        }
        return maxSum;
    }
}
Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

We can observe that two consecutive subarrays of size k share k-1 elements. Instead of re-summing everything, we can 'slide' the window: add the next element (Right) and subtract the element that is no longer in the window (Left).

Pattern: Sliding Window (Fixed Size)

  • Expand: Add nums[right] to windowSum.
  • Shrink/Slide: When right >= k - 1, the window is full. Update the result, then subtract nums[left] and increment left to prepare for the next step.

Mandatory Variables

  • left: Pointer to the start of the window.
  • windowSum: Current sum of the k elements.
  • maxSum: Best sum found so far.
⏱ O(N)💾 O(1)

Detailed Dry Run

StepRightLeftwindowSummaxSumAction
10020Expand
21030Expand
32088Window Full, Update Max
43178Slide (Sub 2, Add 1)
54299Slide (Sub 1, Add 3), Update Max
java
public class Main {
    public static int findMaxSum(int[] nums, int k) {
        int left = 0, windowSum = 0, maxSum = 0;
        for (int right = 0; right < nums.length; right++) {
            // 1. Expand
            windowSum += nums[right];
            
            // 2. Window is full (size k)
            if (right >= k - 1) {
                // 3. Update Result
                maxSum = Math.max(maxSum, windowSum);
                
                // 4. Shrink/Slide
                windowSum -= nums[left];
                left++;
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {2, 1, 5, 1, 3, 2};
        int k = 3;
        System.out.println("Max Sum: " + findMaxSum(nums, k)); // 9
    }
}
← Previous QuestionSplit Array Largest Sum
Next Question →Minimum Size Subarray Sum