#include <iostream>
using namespace std;
int max_subarray_sum(int a[], int N)
{
int maxSum = a[0], sumEach = 0;
int startIndex = 0, endIndex = 0;
for (int i = 0; i < N; i++) {
sumEach = max (a[i], sumEach+a[i]);
//cout << "i " << i << " a[i] " << a[i] << " sumEach " << sumEach << endl;
if (maxSum < sumEach) {
maxSum = sumEach;
if (a[i] == sumEach) {
startIndex = i;
// There can be only one number as a subarray
endIndex = i;
} else {
endIndex = i;
}
// cout << "i " << i << " a[i] " << a[i] << " sumEach " << sumEach << " maxSum " << maxSum << endl;
}
}
cout << "The maximum subarray sum " << maxSum << " index starts at "<< startIndex << " ends at " << endIndex << endl;
return maxSum;
}
int main()
{
/*
* Input : {-2, -9, 5, 0, -1, 8, -2, -3, -4, -1, 0, 3} => sum 12, start 2, end 5
* Input : {-2, -9, 5, 8, -2, -3, -4, -1, 0, 3} => sum 13, start 2, end 3
* Input : {-2, -9, 5, 8, 0, -2, -3, -4, -1, 0, 3} => sum 13, start 2, end 3
* Explanation: considering 0 has no effect
* Input : {-2, -9, 5, 8, 0, 2, -2, -3, -4, -1, 0, 3} => sum 15, start 2, end 5
* Input : {-2, -9, 0, 5, 8, -2, -3, -4, -1, 0, 3} => sum 12, start 2, end 5
* Input : {-2, -9, 5, 0, -1, 8, -2, -3, -4, -1, 0, 3} => sum 12, start 2, end 5
* Input : {-2, -9, -5, 0, -1, -8, -2, -3, -4, -1, 0, -3} => sum 0, start 3, end 3
* Input : {-2, -9, -5, -1, -8, -2, -3, -4, -1, -3} => sum -1, start 3, end 3
* Input : {2, 9, 5, 5, 8, 2, 3, 4, 1, 3} => sum 42, start 0, end 9
* Input : {-2, 1, -3, 4, -1, 2, 1, -5, 4} => sum 6, start 3, end 6
*/
int a[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
/*
* The below is the only way to get array length
* sizeof(a) is 40 here (Eg: 10(number of elements) * 4(integer size))
*/
int n = sizeof(a)/sizeof(a[0]);
int sum = max_subarray_sum(a, n);
//cout << "The maximum subarray sum is " << sum << endl;
return 0;
}
