Carlo Cruz-Albrecht

Maximum Subarray Sum in Linear Time


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

.