Maximum Sum Subarray of Size K — Practice

Problem

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

Examples

Example 1

Input: arr = [2,1,5,1,3,2], k = 3

Output: 9

Explanation: The subarray [5,1,3] has the maximum sum of 9.

Example 2

Input: arr = [2,3,4,1,5], k = 2

Output: 7

Explanation: The subarray [3,4] has the maximum sum of 7.

Constraints

•1 <= k <= arr.length <= 10^5
•1 <= arr[i] <= 10^4

Hints

Hint 1

The naive approach recomputes the sum of each window from scratch — O(n*k). What's being recomputed unnecessarily?

Hint 2

A fixed-size window sliding by one position only changes by two elements: one leaves, one enters.

Hint 3

Maintain a running sum and update it incrementally instead of resumming the whole window each time.

Solutions

public int maxSumSubarrayBruteForce(int[] arr, int k) {
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i + k <= arr.length; i++) {
        int sum = 0;
        for (int j = i; j < i + k; j++) sum += arr[j];
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
}

Time: O(n*k) · Space: O(1)