Problem Statement

Given an array of integers and an integer k, we are to find the maximum sum of a subarray of size k.

Examples

Example 1:

Input: nums = [1, 4, 2, 10, 2, 3, 1, 0, 20], k = 4

Output: 24

Explanation: The subarray [2, 10, 2, 3] has the maximum sum of 24.

Example 2:

Input: nums = [2, 3], k = 2

Output: 5

Explanation: The subarray [2, 3] has the maximum sum of 5.

Different Approaches

1 Brute Force Approach

The brute-force approach involves iterating through all possible subarrays of size k, computing their sums, and returning the maximum sum. While this approach is straightforward, it is not efficient as it has a time complexity of O(n*k), where n is the length of the array and k is the subarray size.

Algorithm:

1. Initialize a variable max_sum to store the maximum sum.
2. Iterate through the array from index 0 to n - k:
   1. Compute the sum of the subarray of size k.
   2. Update max_sum with the maximum of max_sum and the sum of the current subarray.
3. Return max_sum.

Code Implementation in C++:

#include <iostream>
#include <vector>

using namespace std;

int maxSubarraySum(vector<int>& nums, int k) {
    int n = nums.size();
    int max_sum = INT_MIN;

    for (int i = 0; i <= n - k; i++) {
        int sum = 0;
        for (int j = i; j < i + k; j++) {
            sum += nums[j];
        }
        max_sum = max(max_sum, sum);
    }

    return max_sum;
}

Complexity Analysis:

Time Complexity: O(n*k)

Space Complexity:O(1)

2 Sliding Window

The sliding window approach involves maintaining a window of size k and sliding it along the array. We compute the sum of elements within the window and keep track of the maximum sum seen so far. This approach has a time complexity of O(n) and space complexity of O(1).

Algorithm:

1. Initialize left and right pointers to 0.
2. Initialize a variable window_sum to store the sum of elements within the window.
3. Initialize a variable max_sum to store the maximum sum of a subarray of size k.
4. Iterate through the array using the sliding window approach:
   1. Add nums[right] to window_sum.
   2. If the size of the window is equal to k, update max_sum with the maximum of max_sum and window_sum.
   3. If the size of the window exceeds k, subtract nums[left] from window_sum and increment left.
5. Return max_sum.

Code Implementation in C++:

#include <iostream>
#include <vector>

using namespace std;

int maxSubarraySum(vector<int>& nums, int k) {
    int n = nums.size();
    int left = 0, right = 0;
    int window_sum = 0;
    int max_sum = 0;

    while (right < n) {
        window_sum += nums[right];
        if (right - left + 1 == k) {
            max_sum = max(max_sum, window_sum);
            window_sum -= nums[left];
            left++;
        }
        right++;
    }

    return max_sum;
}

Complexity Analysis:

Time Complexity:O(n)

Space Complexity:O(1)

3 Optimized Sliding Window

The optimized sliding window approach improves upon the previous approach by avoiding unnecessary additions and subtractions of elements. Instead of computing the sum of elements within the window from scratch in each iteration, we reuse the sum from the previous window and update it by adding the new element and subtracting the removed element. This approach also has a time complexity of O(n) and a space complexity of O(1).

Algorithm:

1. Initialize left and right pointers to 0.
2. Initialize a variable window_sum to store the sum of elements within the first window of size k.
3. Initialize a variable max_sum to store the maximum sum of a subarray of size k.
4. Iterate through the array using the sliding window approach:
   1. Add nums[right] to window_sum.
   2. If the size of the window is equal to k, update max_sum with the maximum of max_sum and window_sum.
   3. Increment right.
   4. Subtract nums[left] from window_sum and increment left.
5. Return max_sum.

Code Implementation in C++

int maxSubarraySum(vector<int>& nums, int k) {
    int n = nums.size();
    int left = 0, right = 0;
    int window_sum = 0;
    int max_sum = 0;

    for (right = 0; right < k; right++) {
        window_sum += nums[right];
    }
    max_sum = window_sum;

    while (right < n) {
        window_sum += nums[right] - nums[left];
        max_sum = max(max_sum, window_sum);
        left++;
        right++;
    }

    return max_sum;
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity:O(1)