Kadane Algorithm Negative Numbers

Question

int array[] = {-1, 4, -2, 5, -5, 2, -20, 6};

If I had that array, my Kadane algorithm implementation to find the maximum subarray works:

  int max_so_far = INT_MIN;
  int max_ending_here = 0;
  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);
  }

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

However, if I have an array of all negatives:

int array[]= {-10, -10, -10};

It won't work, it should return -10, but I get 0.

How can I make it work for negative numbers too?

Thank you!

Answer 1

When all elements are negative, the maximum subarray is the empty subarray, which has sum 0.

But if you want to change the algorithm to store the greatest element in this case, you could do the following:

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);