The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.
Example, For the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far
In [1]:
data = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
In [2]:
def max_contiguous_subarray(data):
ans = data[0]
max_ending_here = data[0]
for x in data[1:]:
max_ending_here = max(x, max_ending_here + x)
ans = max(ans, max_ending_here)
return ans
In [3]:
print max_contiguous_subarray(data)