In section we saw how to find the maximum subarray sum in O(nlogn) time using a divide and conquer approach (solutions). Here is a way to solve it in linear time:
Given array, let’s define local_max[i] to be the maximum sum of all the subarrays ending with element array[i].
Convince yourself that the max sum of the subarrays ending with array[i] is the max sum of the subarrays ending with array[i - 1] + the element at i. If that number is negative, we return zero since we are considering empty subarrays.
Thus:
local_max[i] = max(0, local_max[i - 1] + array[i])
The max subarray sum of the entire array is the maximum local_max[i] for all indices in the array. Solving for local_max[i] takes constant time assuming we’ve found local_max[i - 1]. (As a base case, define local_max[-1] = 0.) Thus, the total runtime is linear.
Pseudocode:
def max_subarray(array):
local_max = 0
global_max = 0
for i in [0, ..., array.length -1]:
local_max = max(0, local_max[i - 1] + array[i])
if (local_max > global_max):
global_max = local_max
return global_max
.