Kadanes Algorithm for finding sub-array with maximum sum

Here is the Kadanes algorithm implementation in Python. Here we pass thru the array in a linear fashion. While we pass thru the array we keep adding the elements. As we add the elements we keep track of previous largest sum ever found. We compare the present sum with so far largest sum till we finish the entire array.

	#! /usr/env/path python
	class Solution:
	##Complete this function
	#Function to find the sum of contiguous subarray with maximum sum.
	def maxSubArraySum(self,arr,N):
	##Your code here
	if (N < 1) or (N > 1000000):
	print("error : invalid array size")
	return
	max_till_now = arr[0]
	max_ending = 0
	for i in range(len(arr)):
	max_ending = max_ending + arr[i]
	if max_ending < 0:
	if(max_ending > max_till_now):
	max_till_now = max_ending
	max_ending = 0
	elif (max_till_now < max_ending):
	max_till_now = max_ending
	return max_till_now

view raw Kadane.py hosted with ❤ by GitHub