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 maxSumSubarray(int[] arr, int k) {
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
for (int right = k; right < arr.length; right++) {
windowSum += arr[right] - arr[right - k]; // add new element, remove element leaving the window
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}Time: O(n) · Space: O(1)