Given an array of positive integers arr and a positive integer k, find the maximum sum of any contiguous subarray of size exactly k.
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.
1 <= k <= arr.length <= 10^51 <= arr[i] <= 10^4The naive approach recomputes the sum of each window from scratch — O(n*k). What's being recomputed unnecessarily?
A fixed-size window sliding by one position only changes by two elements: one leaves, one enters.
Maintain a running sum and update it incrementally instead of resumming the whole window each time.
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)