Doubt in Kadene's algorithm

#1

Suppose a scenario where all the elements are negetive valued (<0). So what will be the maximum subarray sum? Will it be zero or will it be something negative? In other words, is null considered a subarray?

#2

Kadane’s Algorithm requires at least one positive number, so your all negative array is invalid input.
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;

Sytem.out.println( max_so_far);
#3

could you please send c++ version of this code

#4

i guess, only the last printing statement shall change, so it’s okay. I’ll manage :slight_smile: Thanks again

#5

great :slight_smile: please mark your doubt as resolved