#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;
}