Kadane's algorithm

#1

what if all the array elements are negative. the surrent sum will always remain zero,which is wrong

#2

hey @Keshav99 no if you look at this implementation of the kadane’s algorithm the result is the least negative integer https://ide.codingblocks.com/s/190696

#3

______________thanks, i got it :slight_smile: ______________

#4

hey but i think the algorithm taught in this video is a little wrong

#5

max(cs,ms ) should come first

#6

pls check it out_________________________

#7

@Keshav99
hello keshav which code u are referring,
can u pls post it here

#8 
#include<iostream> 
#include<climits> 
using namespace std; 

int maxSubArraySum(int a[], int size) 
{ 
	int max_so_far = INT_MIN, max_ending_here = 0; 

	for (int i = 0; i < size; i++) 
	{ 
		max_ending_here = max_ending_here + a[i]; 
		if (max_so_far < max_ending_here) 
			max_so_far = max_ending_here; 

		if (max_ending_here < 0) 
			max_ending_here = 0; 
	} 
	return max_so_far; 
} 

int main() 
{ 
	int a[] = {-1, -2, -3, -4}; 
	int n = sizeof(a)/sizeof(a[0]); 
	int max_sum = maxSubArraySum(a, n); 
	cout << "Maximum contiguous sum is " << max_sum; 
	return 0; 
}
#9

@Keshav99
this code is correct and will handle all negative case as well

#10

@aman212yadav i guess in the code that he is referring to,

if (max_so_far < max_ending_here) 
	max_so_far = max_ending_here;

This comparison is not the first comparison but is the second comparison.