c++algorithmkadanes-algorithm

Kadane Algorithm Negative Numbers

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!

Solution

  • According to Wikipedia, Kadane's Algorithm requires at least one positive number, so your all negative array is invalid input.