So kadane's algorithm is to find the maximum sum of continuous numbers in a 1D array (i.e you're finding a subarray).
What's special about this you ask?
Well its complexity is of O(n)
Here's a simple pseudocode.
First: max = 0
max_end = 0
For each element of the array:
(a) max_end = max_end + a[i]
(b) if(max_end < 0) max_end = 0
(c) if(max < max_end) max = max_end return max
So basically we're looking for a list of positive numbers.
If a negative number appears when max_end==0, we don't need to start counting the sum as the negative number will be less than zero, and we're trying to maximize the sum.
Otherwise if the max_end is greater than max, update the new value of max to max_end.
Check this example.
Eg -3,2,4,-3,6
Firstly -3 appears, so since max_end now equals -3, we make max_end=0.
Next 2 comes up, so max_end=2 and since max_end>max make max=2.
Next 4 comes up, so max_end=2+4=6 and since max_end>max make max=6.
Next -3 comes up, so max_end=6-3=3 and since max_end<max retain max=6.
Next 6 comes up, so max_end=3+6=9 and since max_end>max make max=9.
Hence our maximum sum of numbers in the subarray is from i=1 to i=4 which totals upto 9.
This algorithm can be used in a variety of programming problems.
If a negative number appears when max_end==0, we don't need to start counting the sum as the negative number will be less than zero, and we're trying to maximize the sum.
Otherwise if the max_end is greater than max, update the new value of max to max_end.
Check this example.
Eg -3,2,4,-3,6
Firstly -3 appears, so since max_end now equals -3, we make max_end=0.
Next 2 comes up, so max_end=2 and since max_end>max make max=2.
Next 4 comes up, so max_end=2+4=6 and since max_end>max make max=6.
Next -3 comes up, so max_end=6-3=3 and since max_end<max retain max=6.
Next 6 comes up, so max_end=3+6=9 and since max_end>max make max=9.
Hence our maximum sum of numbers in the subarray is from i=1 to i=4 which totals upto 9.
This algorithm can be used in a variety of programming problems.
