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

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

Well Kadane's algorithm does not work for the case when all the elements of an array are negative. It simply returns 0 in that case. In case if you wanted the for handling this we need to add extra phase before actual implementation. The phase will look if all numbers are negative, if they are it will return maximum of them (or smallest in terms of absolute value).

I can suggest one implementation

#define find_max_val(x,y) x >= y ?x :y;

int min_sum(int a[],int n){
int min_so_far = a[0],min_end_here = a[0];

for(int i = 1;i < n; i++){

    min_end_here = find_max_val(a[i],min_end_here + a[i]);
    min_so_far = find_max_val(min_so_far,min_end_here);
}

return min_so_far;
}

there are still other implementations depending upon ones need.

Answer 6

if we have an array of all negatives, then the max element in the array will be the result.
For eg : if the array elements are
-3 -2 -5 -4 -1

The largest sum subarray is -1.

just an O(n) search.

Code:

int maxSubArraySum(int array[], int size) { 
    int max_sum = INT_MIN, max_ending_here = 0; 
    
    for (int i = 0; i < size; i++) { 
        max_ending_here += a[i]; 
        if (max_sum < max_ending_here) {
            max_sum = max_ending_here; 
        }
        max_ending_here = max(max_ending_here, 0);
    } 
    return max_sum; 
} 

Answer 7

If all the elements are negative, then return the least negative number. In all other cases, your solution will work just fine.

printf("%d\n",max(max_so_far, *max_element(array,array+size)) );

Answer 8

According to WIKI

public int maxSubArray(int[] nums) {
    int currentSum = 0;
    int bestSum = 0;

    for (int element : nums) {
        currentSum = Math.max(0, currentSum + element);
        bestSum = Math.max(bestSum, currentSum);
    }

    return bestSum;
}

The above code will fail for the input

nums = [-1]

According to WIKI again

This version of the algorithm will return 0 if the input contains no positive elements (including when the input is empty). For the variant of the problem which disallows empty subarrays, best_sum should be initialized to negative infinity instead and also in the for loop current_sum should be updated as max(x, current_sum + x). In that case, if the input contains no positive element, the returned value is that of the largest element (i.e., the least negative value), or negative infinity if the input was empty.

Modified code for negative inputs:

public int maxSubArray(int[] nums) {
    int currentSum = 0;
    int bestSum = Integer.MIN_VALUE;

    for (int element : nums) {
        currentSum = Math.max(element, currentSum + element);
        bestSum = Math.max(bestSum, currentSum);
    }

    return bestSum;
}

Answer 9

Please refer to wikiped kadane's algorithm max subarray

 int max_subArray(Integer[] input){
    int max_so_far,max_ending_here;
    max_so_far = max_ending_here =input[0];

    for(int i =1; i<input.length;i++){
        max_ending_here = Math.max(input[i], input[i]+max_ending_here);
        max_so_far = Math.max(max_so_far, max_ending_here);
    }

    return max_so_far;      
}

And it will return -10 in your case

Answer 10

This is another option for achieving your goal

int Solution::maxSubArray(const vector<int> &A){
    int cs=0,ms=0,l=A.size(),x=0,min;
    if(A[0]<0)
        min=A[0];
        x++;
    if(l==1)
        return A[0];
    for(int i=1;i<A.size();i++){
        if(A[i]<0)
            x++;
        if(A[i]>min)
            min=A[i];
        else
            break;
      }
    if(x==l)
        return min;
    for(int i=0;i<A.size();i++){
        cs=cs+A[i];
        if(cs<0)
        cs=0;
        ms=max(cs,ms);
    }
return ms;
}

Answer 11

Here is my approach, have used extra 2 variables

public int maxSubArray(int[] nums) {
  int max_so_far = 0;
  int max_ends_here = 0;
  int largestNeagtive = Integer.MIN_VALUE;
  boolean isAllNegativeNumbers = true;
    
  for (int i = 0; i < nums.length; i++) {
    max_ends_here += nums[i];      
    if (max_ends_here < 0) max_ends_here = 0;
    if (max_so_far < max_ends_here) max_so_far = max_ends_here;
    if (isAllNegativeNumbers && nums[i] >= 0) isAllNegativeNumbers = false;
    if (nums[i] < 0  && nums[i] > largestNeagtive) largestNeagtive = nums[i];
  }
  return isAllNegativeNumbers ? largestNeagtive : max_so_far;
}

Answer 12

I'm late to this party, but would something like this work?:

cur_sum = max_sum = sequence[0];
sum_to_j = 0;
for j in range(0, len(sequence)):
    sum_to_j += sequence[j];
    if sum_to_j > cur_sum:
        cur_sum = sum_to_j;
    if cur_sum > max_sum:
        max_sum = cur_sum
    if sum_to_j < 0:
        sum_to_j = 0;
        cur_sum = sequence[j];
print max_sum;

Answer 13

If all the elements are negative,Return the largest element by value

    boolean allNegative = true;
    int bigNegative = Integer.MIN_VALUE;

    int maxSum = 0;
    int sum =  0;
    for(int i=0;i<a.size();i++){
        // if all numbers are negative
        if(a.get(i)>=0){
            allNegative = false;
        }else{
        if(a.get(i)>bigNegative){
            bigNegative = a.get(i);
        }

        }
    sum += a.get(i);
    if(sum<0){
        sum=0;
    }
    if(sum>maxSum){
        maxSum = sum;
    }

    }
    if(allNegative){
        return bigNegative;
    }
    return maxSum;

Answer 14

It works with the below code.

public int algorithmKadane(int[] input_array){
int sum = input_array[0];
int rotate_sum = input_array[0];
for(int i=1; i< input_array.length ; i++){ 
rotate_sum = Math.max(input_array[i], rotate_sum+input_array[i]);
sum = Math.max(rotate_sum,sum);
}
return sum;
}

Answer 15

Hope this solution would work to handle all negative numbers case too for Kadane's Algo

    long long int n,max_f=0,i,max_end=0,s;
    cin>>n;
    long long int a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    long long int *m;
    m=max_element(a,a+n);
    if(*m<0)
    {
        s=*m;

    }
    else {

        for(i=0;i<n;i++)
        {
            max_end= max_end +a[i];
            if(max_end<0)
            {
                max_end=0;
            }
            if(max_f < max_end)
            {
            max_f=max_end;
            }
            s=max_f;
        }
    }
    cout<<s<<endl;
}

Answer 16

        public static int max_sum(int[] in){

        int maxsum=0;
        int cursum=0;
        for (int i=0;i<in.length;i++){
            cursum = in[i]+cursum;
            if (cursum>maxsum) {
                maxsum = cursum;
            }

//            for negative value
            if (cursum < 0) {
                for (int n=0;n<in.length;n++){
                    maxsum = in[n];
                    if (cursum>maxsum){
                        maxsum=cursum;
                    }
                }
            }
        }
        return maxsum;
    }

Answer 17

int maxSub(vector<int> x){
    int current_max=0,overall_max=INT_MIN;
    for(int i=0;i<x.size();i++){
        current_max+=x[i];
        if(overall_max<current_max)
            overall_max=current_max;
        if(current_max <0)
            current_max=0;
    }
    return overall_max;
}