Sliding Window Algorithm

Description

The Sliding Window algorithm is used for finding subarrays of a given size k with the maximum sum or minimum sum efficiently. It involves maintaining a window of size k over the array and sliding it from left to right by one element at a time, adjusting the sum of the window based on the addition of the new element and removal of the old element.

C++ Code

#include <iostream>
#include <vector>
using namespace std;

int maxSumSubarray(int arr[], int n, int k) {
    int max_sum = 0;
    for (int i = 0; i < k; i++) {
        max_sum += arr[i];
    }

    int window_sum = max_sum;

    for (int i = k; i < n; i++) {
        window_sum += arr[i] - arr[i - k];
        max_sum = max(max_sum, window_sum);
    }

    return max_sum;
}

int main() {
    int arr[] = {1, 4, 2, 10, 2, 3, 1, 0, 20};
    int k = 4;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum of a subarray of size " << k << ": " << maxSumSubarray(arr, n, k) << endl;
    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Sliding Window Algorithm	O(n)	O(1)

Where:

• n: Size of the input array.

← Back to Homepage