Implementation of Kadane Algorithm in Python

1. Let n be the size of array
2. set: max_sum_so_far=arr[0]
3. set: max_here=0
4. do For i=0 to n-1:
5.       set: max_here=max_here+arr[i]
6.       If  max_sum_so_far<max_here:
7.               set: max_sum_so_far=max_here
8.       If  max_here<0:
9.               set: max_here=0
10. End ForLoop
11. return max_sum_so_far

Explanation of Algorithm:

Let arr[]= { 4, 5, -1, -3,  6, -7 }

Set: max_sum_so_far = arr[0]   // max_sum_so_far will keep the maximum sum we have ever                                                             seen in the array.
Set: max_here = 0                         // max_here will keep the sum till ith element of the array.

Pass 1, i=0:      arr[0]= 4,   max_here=4, max_sum_so_far=4
Pass 2, i=1:      arr[1]= 5,   max_here=9, max_sum_so_far=9
Pass 3, i=2:      arr[2]= -1,  max_here=8, max_sum_so_far=9
Pass 4, i=3:      arr[3]= -3,  max_here=5, max_sum_so_far=9
Pass 5, i=4:      arr[4]=  6,  max_here=11, max_sum_so_far=11
Pass 6, i=5:      arr[5]= -7,  max_here=4,  max_sum_so_far=11

Therefore, contiguous sub-array with maximum sum is { 4, 5, -1, -3, 6} with sum=11

Implementation of Kadane Algorithm in Python is given below

```def kadane():
max_sum_so_far=listing[0]
max_here=0
for i in range(0,len(listing)):
max_here=max_here+listing[i]
if(max(max_sum_so_far,max_here)==max_here):
max_sum_so_far=max_here
if(max_here<0):
max_here=0
return max_sum_so_far
global listing
listing=[]
listing=list(map(int, raw_input().split()))