Kadane's algorithm all negative

#1

here the case with all -ve numbers has not been handled right?

#2

Yes this will not work when all array elements are negative.
In that case answer will simply be the least negative number

#3

how can we modify this to get the start and end index of the sub-array containing the max sum?

#4

To print the maximum subarray, along with maintaining the maximum subarray sum, also maintain the indices whenever you get maximum subarray sum so far.
The function would be something like this:

int maxSubArraySum(int a[], int size)
{
int max_so_far = INT_MIN, max_ending_here = 0,
start =0, end = 0, s=0;
for (int i=0; i< size; i++ )
{
max_ending_here += a[i];
if (max_so_far < max_ending_here)
{
max_so_far = max_ending_here;
start = s;
end = i;
}
if (max_ending_here < 0)
{
max_ending_here = 0;
s = i + 1;
}
}
cout << "Maximum contiguous sum is "
<< max_so_far << endl;
cout << "Starting index "<< start
<< endl << "Ending index "<< end << endl;
}

#5

great, I exactly wanted this.