Kadane's algo to find max subarray aum

#1

the code is not working when all the array elements are negative. It is returning 0. but it should return the highest element(negative).

#2

Plz send your code by saving on ide

#3

hey @ankityadav943, this is the disadvtage of kadane algo that it gives 0 when all numbers are negative. But you can modify the kadane code to give highest element. Refer this

int max_so_far = INT_MIN;
int max_ending_here = 0;
int max_element = INT_MIN;

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

if (max_so_far == 0)
max_so_far = max_element;

printf("%d\n", max_so_far);

1 Like
Maximum subarray sum maxum=0 initialisation
#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like
#5

its simple if all the elements are -ve then the answer will be the least -ve number itself,that we can find in an array easily.