Kadane Algorithm Negative Numbers

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

int max_so_far = INT_MIN;
int max_ending_here = array[0];
for (int i = 1; i < size; i++) {
    max_ending_here = max(max_ending_here + array[i], array[i]);
    max_so_far = max(max_ending_here, max_so_far);
 }
 printf("%d\n", max_so_far);

It may works

Make a slight addition to Kadane's algo. Take a flag, are_all_elements_negative(set to true) and an int(store the highest -ve integer) while iterating over the array, if you find a positive number, set the flag false. While the flag is true, store the highest -ve num. At the end,check the flag, if the flag is true,output the -ve integer, else output the regular Kadane's algo output.

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