Maximum subarray in one pass

Coding Challenges
,
1

Problem. Given an integer array nums, return the largest sum of any non-empty contiguous subarray.

Example:

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

The best subarray is [4, -1, 2, 1], so the answer is 6.

This is the classic Kadane’s algorithm interview problem.

Solution. Scan left to right while tracking:

  • current: the best subarray sum that must end at the current index
  • best: the best subarray sum seen anywhere so far

At each value, either extend the previous subarray or start fresh at the current element.

def maximum_subarray(nums):
	current = nums[0]
	best = nums[0]

	for value in nums[1:]:
		current = max(value, current + value)
		best = max(best, current)

	return best

Runtime is O(n) and extra space is O(1).

Gotchas.

  • The subarray must be non-empty, so initialize from nums[0] rather than 0.
  • In an all-negative array, the answer is the largest single element.
  • The circular-array follow-up is different and needs extra logic.

Run: maximum subarray