Kadane's Algorithm

#1

Kadane’s algorithm works only if the sum of subarray is positive. How do I improvise the code such that Kadane’s algo works even when all the elements of an array are negative?

#2

hello @meer

initilise ur max_so_far variable with arr[0] (or any element of the array ) and then it should work.

#3

It doesn’t seem to work! The output is zero! ( I’m attaching the code: int main() { int n; cout<<"Value of n: "; cin>>n; int arr[n]; for(int i=0;i<n;i++) cin>>arr[i]; int current_sum=0; int maxsum=arr[0]; for(int i=0;i<n;i++) { current_sum+=arr[i]; if(current_sum<0) current_sum=0; maxsum=max(current_sum,maxsum); } cout<<"largest sum: "<<maxsum; })

#4

please share ur code using cb ide, i will check

#5

CODE URL:

#6

check now->

#7

Ohkay!!
It’s working!
Thankyou :slight_smile:

#8

@meer, have you reopened your doubt ??

#9

No! It’s been resolved