Tackling all Negative values array in Kadane algo

#1

In Kadane algo if any currentSum value comes out as negative we assign the value of currentSum as 0
What if we give an all negative element array?
like: - 4, - 5, - 1, - 7
In above case maximum sum should be -1 but if we use kadane algorithm then it would be 0. How to tackle this situation??

#2

Okay, so for this, what we can do is initialise cumulative sum with INT_MIN, this will handle this case.

#3

Sure, I’ll code and check the results using INT_MIN.

#4

Actually there’s no cumulative sum in Kadane’s algorithm so we cannot initialize it to INT_MIN. We compare if a negative value is there and replace the current sum by 0 if it is there and so on…

#6 
int max_subarray_sum(int a[], int n){
  int current_max = 0;
  int max_so_far = INT_MIN;
  for(int i=0; i<n; i++){
     current_max = max(current_max + a[i], a[i]); 
     max_so_far = max(current_max, max_so_far);
   }
   return max_so_far;
}
Maximum Subarray Sum
#7

Yes, I understood the code and it’s working perfectly!

I also have some other doubts:

  1. How can we effectively find indexes of the array elements to print our maximum array along with the maximum sum of subarray? I did it myself but I’m trying to find alternate approaches to do it.

  2. What if there are two arrays having same sum, then what should our array elements be?
    like eg 4 5 -9 2 3 4
    here 4 + 5 = 9 is max value
    but also 2 + 3 + 4 = 9 is max value
    Here, if we print the array using indexing the answer would be 4, 5, so would that be right? or the answer should be 2, 3, 4? or both are correct?

#8

both are correct

that’s the only effective way.

#9

Sure, I understood it now!!
Thanks for clearing my doubts.

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.