What if all the array elements are negative?

[sahasoumyajit2020 (Soumyajit Saha)]

if all the nos are negative then max sum should be smallest negative number.
for ex, if the array is
-1 -5 -7 -3 -8 ,then here the maximumsum of the subarray should be -1 but with kadane’s algorith the maximum sum will be 0 which is wrong i guess

[aman212yadav (Aman Yadav)]

hello @sahasoumyajit2020

@sahasoumyajit2020

if all the nos are negative then max sum should be smallest negative number.
for ex, if the array is
-1 -5 -7 -3 -8 ,then here the maximumsum of the subarray should be -1 but with kadane’s algorith the maximum sum will be 0 which is wrong i guess

yeah correct.

u can modify its implementation a bit , to make it work for evry cases.

int max_so_far      = array[0];
int max_ending_here = 0;


for (int i = 0; i < size; i++)
{
    max_ending_here =max_ending_here + array[i];
    max_so_far      = max(max_ending_here, max_so_far);
    max_ending_here = max(max_ending_here, 0);

}