Solution: Maximum Sum Subarray of Size K

Blind 75

Problem Statement

Given an array of positive numbers and a positive number 'k,' find the maximum sum of any contiguous subarray of size 'k'.

Example 1:

Input: arr = [2, 1, 5, 1, 3, 2], k=3 
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3].

Example 2:

Input: arr = [2, 3, 4, 1, 5], k=2 
Output: 7
Explanation: Subarray with maximum sum is [3, 4].

Solution

To solve this problem, we will use a brute force approach. The brute force method involves examining every possible subarray of size k and calculating their sums. We then keep track of the highest sum found. This approach is simple to understand and implement, making it a good choice for smaller arrays or when performance is not a concern. However, it may not be the most efficient for larger arrays due to its higher time complexity.

The brute force approach works by iterating through each possible starting index of a subarray of size k. For each starting index, we calculate the sum of the subarray by iterating through the next k elements. We update our maximum sum whenever we find a new subarray with a higher sum. While this method ensures we find the maximum sum, it involves a nested loop, leading to a higher computational cost.

Step-by-Step Algorithm

Initialize Variables:
- maxSum to store the maximum sum encountered, initially set to 0.
- windowSum to store the sum of the current subarray of size k.
Outer Loop:
- Iterate from the start of the array to arr.Length - k. This ensures we have enough elements left to form a subarray of size k.
Reset windowSum:
- For each new starting index i, set windowSum to 0.
Inner Loop:
- Iterate from the current starting index i to i + k - 1.
- Add each element to windowSum to compute the sum of the current subarray.
Update maxSum:
- After computing the sum of the current subarray, update maxSum if windowSum is greater.
Return maxSum:
- After completing both loops, maxSum will contain the highest sum of any subarray of size k.

Algorithm Walkthrough

Using the array [2, 1, 5, 1, 3, 2] and K = 3:

Initialization:
- maxSum = 0
Outer Loop Iteration:
- i = 0:
  - windowSum = 0
  - Inner Loop:
    - j = 0: windowSum += 2 → windowSum = 2
    - j = 1: windowSum += 1 → windowSum = 3
    - j = 2: windowSum += 5 → windowSum = 8
  - Update maxSum: maxSum = Math.Max(0, 8) → maxSum = 8
- i = 1:
  - windowSum = 0
  - Inner Loop:
    - j = 1: windowSum += 1 → windowSum = 1
    - j = 2: windowSum += 5 → windowSum = 6
    - j = 3: windowSum += 1 → windowSum = 7
  - Update maxSum: maxSum = Math.Max(8, 7) → maxSum = 8
- i = 2:
  - windowSum = 0
  - Inner Loop:
    - j = 2: windowSum += 5 → windowSum = 5
    - j = 3: windowSum += 1 → windowSum = 6
    - j = 4: windowSum += 3 → windowSum = 9
  - Update maxSum: maxSum = Math.Max(8, 9) → maxSum = 9
- i = 3:
  - windowSum = 0
  - Inner Loop:
    - j = 3: windowSum += 1 → windowSum = 1
    - j = 4: windowSum += 3 → windowSum = 4
    - j = 5: windowSum += 2 → windowSum = 6
  - Update maxSum: maxSum = Math.Max(9, 6) → maxSum = 9
Result:
- The final maxSum is 9, which is the maximum sum of any subarray of size k = 3.

Code

Here is what our algorithm will look like:

Python3

Complexity Analysis

Time Complexity

Outer loop: The outer loop runs for each possible starting index of a subarray of size K. The number of such subarrays is $N - K + 1$ , where N is the length of the array. This means the outer loop runs approximately $O(N)$ times.
Inner loop: For each iteration of the outer loop, the inner loop runs exactly K times to calculate the sum of the current subarray. So, for each outer loop iteration, we spend $O(K)$ time calculating the sum of the subarray.
Therefore, the total time complexity is $O(N \times K)$ because for each subarray, we are doing $O(K)$ work to compute its sum.

Overall time complexity: $O(N \times K)$ .

Space Complexity

Additional variables: The algorithm only uses a few extra variables, such as maxSum and windowSum, both of which require constant space. No additional data structures that depend on the input size are used.

Overall space complexity: $O(1)$ .

Is it possible to find a better algorithm than this?

A Better Approach

To solve this problem, we will use a sliding window technique. This approach allows us to maintain the sum of the current subarray of size K, and as we move through the array, we update this sum by subtracting the element that is no longer in the subarray and adding the next element in the array. This method is effective because it avoids the need to repeatedly sum elements for overlapping subarrays, thus reducing the time complexity to linear time, O(n). By keeping track of the maximum sum encountered, we ensure that we can efficiently find the solution.

The sliding window approach works well because it maintains a running sum of a fixed number of elements. This avoids the inefficiencies of recalculating sums for each subarray, which would be necessary if we were to use a brute force method. The efficiency and simplicity of updating the sum as we slide the window over the array make this approach optimal for this problem.