Maximum Sum Subarray of Size K

Given an integer array nums and an integer k, find the maximum sum of any continuous subarray of size k.

A subarray is a contiguous part of the array.

Return the maximum sum among all subarrays of size k.

If no subarray of size k exists, return -1.

Brute Force Approach

Every possible starting position can form at most one subarray of size k. Calculating the sum of k consecutive elements from each valid starting position guarantees examination of every possible fixed-size subarray.

Overlapping subarrays contain many common elements. Recalculating every sum from the beginning repeats additions, producing a simple but inefficient solution.

Algorithm

• Store the array size in n and return -1 when k <= 0 or n < k because no valid subarray can exist.

• Initialize maxSum with the smallest possible value to support arrays containing only negative numbers.

• Traverse every valid starting index i from 0 to n - k.

• Initialize currentSum with 0 and add elements from index i through i + k - 1.

• Update maxSum with the larger value between maxSum and currentSum after calculating each complete window.

• Return maxSum after examination of every subarray of size k.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N × K), where N represents the array size. Every valid starting position may require addition of K elements.

Space Complexity: O(1), because only loop indices, currentSum, and maxSum require auxiliary storage.

Better Approach

A prefix sum array stores cumulative sums from the beginning of nums. The value at prefixSum[i] represents the sum of the first i elements.

For a subarray starting at index i and ending at index i + k - 1, subtracting prefixSum[i] from prefixSum[i + k] removes all elements before index i. Every fixed-size subarray sum can therefore be calculated in constant time.

Algorithm

• Store the array size in n and return -1 when k <= 0 or n < k.

• Create prefixSum with size n + 1 and initialize prefixSum[0] with 0.

• Traverse nums and calculate prefixSum[i + 1] = prefixSum[i] + nums[i].

• Initialize maxSum with the smallest possible value to support negative subarray sums.

• Traverse every starting index i from 0 to n - k, calculate currentSum = prefixSum[i + k] - prefixSum[i], and update maxSum.

• Return maxSum after processing every valid starting position.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), where N represents the array size. Prefix construction requires O(N) time, and examination of all fixed-size subarrays requires O(N) time.

Space Complexity: O(N), because prefixSum stores N + 1 cumulative values.

Optimal Approach

A fixed-size window can begin with the first k elements. Moving the window one position forward removes the leftmost element and includes one new element from the right.

Subtracting the outgoing element and adding the incoming element updates the window sum without recalculating all k values. Every element enters and leaves the window at most once.

Algorithm

• Store the array size in n and return -1 when k <= 0 or n < k, because no subarray of exactly k elements can be formed.

• Initialize windowSum with 0 and add the first k elements so it represents the sum of the first valid window.

• Initialize maxSum with windowSum, since the first window provides the first valid candidate and also handles arrays containing only negative values.

• Traverse i from k to n - 1, where nums[i] is the new element entering the window and nums[i - k] is the element leaving from its left side.

• Update windowSum by adding nums[i] and subtracting nums[i - k], then update maxSum whenever the new window produces a larger sum.

• Return maxSum after every fixed-size window has been processed.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N), where N represents the array size. Initial window construction processes K elements, while the remaining traversal processes every later element once.

Space Complexity: O(1), because only windowSum, maxSum, and loop variables require auxiliary storage.

FAQS

Q1. Why does the prefix sum approach improve upon brute force?

Prefix sums calculate every subarray sum through one subtraction, avoiding repeated addition of K elements.

Q2. Why does prefixSum contain N + 1 positions?

The leading zero allows every subarray sum, including a subarray starting at index 0, to use the same subtraction formula.

Q3. Why is nums[i - k] removed during sliding-window traversal?

Index i - k represents the leftmost element of the previous window. Removal maintains exactly K elements inside the new window.

Q4. Does the sliding-window approach support negative values?

Yes. Initialization from the first valid window prevents an incorrect default answer of 0 for arrays containing only negative values.

Q5. What happens when k equals the array size?

Only one valid subarray exists, so the sum of the complete array becomes the answer.