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

1. 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.

2. 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.

3. Reset windowSum:

   • For each new starting index i, set windowSum to 0.

4. 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.

5. Update maxSum:

   • After computing the sum of the current subarray, update maxSum if windowSum is greater.

6. 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:

1. Initialization:

   • maxSum = 0

2. 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

3. 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:

Complexity Analysis

• Time Complexity: The time complexity of this algorithm is O(n * k). The outer loop runs n - k + 1 times, and the inner loop runs k times for each iteration of the outer loop.
• Space Complexity: The space complexity is O(1). We use a fixed amount of extra space, regardless of the input size. We only store a few variables (maxSum and windowSum).

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.

Step-by-Step Algorithm

1. Initialize Variables:
   • windowSum to store the sum of the current window of size k.
   • maxSum to store the maximum sum encountered.
   • windowStart to mark the start of the current window.
2. Iterate through the array:
   • Use a for loop where windowEnd goes from 0 to the end of the array.
3. Add the current element to windowSum:
   • windowSum += arr[windowEnd]
4. Check if we have hit the window size:
   • If windowEnd is greater than or equal to k-1, perform the following steps:
5. Update maxSum:
   • Set maxSum to the greater of maxSum and windowSum: maxSum = Math.Max(maxSum, windowSum)
6. Slide the window:
   • Subtract the element at windowStart from windowSum: windowSum -= arr[windowStart]
   • Increment windowStart by 1 to slide the window: windowStart++
7. Return maxSum:
   • After the loop ends, maxSum will contain the maximum sum of any subarray of size k.

Algorithm Walkthrough

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

1. Initialization:

   • windowSum = 0
   • maxSum = 0
   • windowStart = 0

2. Iteration:

   • windowEnd = 0:
     • Add arr[0] (2) to windowSum: windowSum = 2
   • windowEnd = 1:
     • Add arr[1] (1) to windowSum: windowSum = 3
   • windowEnd = 2:
     • Add arr[2] (5) to windowSum: windowSum = 8
     • Since windowEnd is >= k-1:
       • Update maxSum = Math.Max(0, 8) = 8
       • Subtract arr[0] (2) from windowSum: windowSum = 6
       • Increment windowStart: windowStart = 1
   • windowEnd = 3:
     • Add arr[3] (1) to windowSum: windowSum = 7
     • Since windowEnd is >= k-1:
       • Update maxSum = Math.Max(8, 7) = 8
       • Subtract arr[1] (1) from windowSum: windowSum = 6
       • Increment windowStart: windowStart = 2
   • windowEnd = 4:
     • Add arr[4] (3) to windowSum: windowSum = 9
     • Since windowEnd is >= k-1:
       • Update maxSum = Math.Max(8, 9) = 9
       • Subtract arr[2] (5) from windowSum: windowSum = 4
       • Increment windowStart: windowStart = 3
   • windowEnd = 5:
     • Add arr[5] (2) to windowSum: windowSum = 6
     • Since windowEnd is >= k-1:
       • Update maxSum = Math.Max(9, 6) = 9
       • Subtract arr[3] (1) from windowSum: windowSum = 5
       • Increment windowStart: windowStart = 4

3. Result:

   • The final maxSum is 9, which is the maximum sum of any subarray of size k = 3.

Code

Complexity Analysis

• Time Complexity: The time complexity of this algorithm is O(n). This is because we pass through the array only once, updating the sum in constant time for each element.
• Space Complexity: The space complexity is O(1). We use a fixed amount of extra space, regardless of the input size. We only store a few variables (such as maxSum and windowSum).