Kadane's Algorithm

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.

Kadane’s Algorithm: 
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.