Max Sum Subarray of size K

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find maximum sum subarray of exactly size k. Sliding window.

Algorithm

1Compute sum of first k elements. Slide: add next, remove leftmost. Track maximum.

Common Pitfalls

•Classic fixed-size sliding window. O(n). Initial window sum then slide.

Max Sum Subarray of size K.java

Java

// Approach: Sliding window of fixed size k. Compute sum of first k elements, then
// slide: add new element and remove leftmost element. Track maximum sum seen.
// Time: O(n) Space: O(1)
class Solution {
    public int maxSubarraySum(int[] arr, int k) {
        int n = arr.length;

        int windowSum = 0;
        int maxSum = 0;

        for (int i = 0; i < k; i++)
            windowSum += arr[i];

        maxSum = windowSum;

        for (int i = k; i < n; i++) {
            windowSum += arr[i];
            windowSum -= arr[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }
}

Was this solution helpful?