Kadane’s Algorithim is used to find the maximum sum of a sub-array with an array of integers. E.g.
input: [-2,1,-3,4,-1,2,1,-5,4]
max is 6, and the "best" subarray is [4, -1, 2, 1]
The algorithm rests on the idea the the max sub array sum will either be the max of either the current pointer (single element of the pointer) or the local maximum and the current pointer.
Any negative sum in previous sub array doesn’t contribute and therefore can be ignored.
solution
def maxSubArray(arr):
if len(arr) == 0:
return 0
local_max, max_sum = arr[0]
for num in arr[1:]:
local_max = max(num, num + local_max)
max_sum = max(max_sum, local_max)
return max_sum