Kadane's Algo Alternative

#1

Kadane’s algorithm for maxm subarray sum is okay for an array containing a mix of both +ve and -ve numbers or when there are only +ve numbers. But a test case may pop up that has all -ve numbers like {-9, -8, -6, -3, -1} or anything like that and we might be required to output -1 (basically when empty subarray is not a valid option).

For that, i have written this function. Please see and check if it can be made better.

int maxSubarraySum(int ar[], int n){
int lowestSoFar = ar[0], maxSum = INT_MIN;
for(int i = 1; i < n; i++){
ar[i]+=ar[i-1];
maxSum = max(maxSum, ar[i]-lowestSoFar);
lowestSoFar = min(lowestSoFar, ar[i]);
}
return maxSum;
}

and the same thing can be converted to Kadane’s algorithm by swapping the reassignment statements of maxSum and lowestSoFar.

#2

Please run your code for different input sets:

5
-1 -2 -3 -4 -5

output should be : -1
But your code is printing -2.

Correct it, else it is a good approach.

#3

if we change it slightly by initializing maxSum with ar[0] before the loop, it’s working.

int maxSubarraySum(int ar[], int n){
int lowestSoFar = ar[0], maxSum = ar[0];
for(int i = 1; i < n; i++){
ar[i]+=ar[i-1];
maxSum = max(maxSum, ar[i]-lowestSoFar);
lowestSoFar = min(lowestSoFar, ar[i]);
}
return maxSum;
}

now is it ok?

#4

Nope,
It’s not working correct.
This code works only if all the elements are negative.

5
2 3 3 4 1
Run your code on above input.

Before asking for doubt, please check your code for all possible test cases i.e. all positive, all negative, and mixture.
if it works, then there’s the code you were looking for.
else, may be your approach is wrong.

#5

How about now? I tried test cases using all +ve, all -ve, mixture and zeroes. Please see if it is correct now…
int maxSubarraySum(int ar[], int n){
int lowestSoFar = min(0, ar[0]), maxSum = ar[0];
for(int i = 1; i < n; i++){
ar[i]+=ar[i-1];
maxSum = max(maxSum, ar[i]-lowestSoFar);
lowestSoFar = min(lowestSoFar, ar[i]);
}
return maxSum;
}

#6

Excellent. :clap:
I am impressed by your hard work and determination.
Keep this love and interest of yours for coding.

If you are satisfied, give a like and mark this doubt as resolved.

1 Like