Maximum SubArray Problem (Sliding Window Technique)

This algorithm 'Sliding Window Technique' will be used when we want to calculate the sum in a specific range of subarray. If this range is not given, we can go with Kadane's Algorithm mentioned here.

Each subarray is considered as window, so once the sum is calculated for the subarray, window will be slided to the next window.

Please click here to debug and explore more.

#include <iostream>

using namespace std;

int maxSubArraySum(int arr[], int k, int size) 
{
    int maxSum = 0, localSum = 0, start = 0, end = 0;
    for (int i = 0; i < size; i++) {
        //cout << " arr[" << i << "] " << arr[i] << endl;
        if (i < k) {
           localSum += arr[i]; 
        } else {
            localSum = localSum - arr[i-k] + arr[i];
            //cout << "Slide localSum " << localSum << " a[i] " 
                   << arr[i] << endl;
        } 
        if (maxSum < localSum) {
            maxSum = localSum;
            start = i- k + 1; 
            end = i;
        }
        //cout << " arr[" << i << "] " << " localSum " << localSum 
               << " maxSum " << maxSum << endl;
    } 
    cout << "The sum is " << maxSum << " starts at " << start 
         << " and ends at " << end << endl;
    return maxSum;
}

int main()
{
    /*
     * Considering indices from 0
     * Input : {5, 2, 10, 10, 3, 8, 9} Output : 23, index 2 -> 4
     * Input : {5,4,8,7,6,3,2,1} Output : 21, index 2 -> 4
     * Input : {8,7,6,5,4,3,2,1} Output : 21, index 0 -> 2
     * Input : {1,2,3,4,5,6,7,8} Output : 21, index 5 -> 7
     */
    int arr[] = {1,2,3,4,5,6,7,8}; 
    int size = sizeof(arr)/sizeof(arr[0]);
    int sum = maxSubArraySum(arr, 3, size);
    //cout << "The sum is " << sum << endl;
    return 0;
}

Time Complexity : O(n)

To learn more about sliding window, click here. 

Other Sliding Window Problems:

Longest Substring without repeating characters

Longest substring with replacement (#424 Leetcode)