Introduction

Here we try to solve the Maximum Subarray problem step by step until we work out the O(n) solution.

Code is written in Go.

List all subarrays and find the maximum sum <-- O(n³)

First, in a very naive way, we can just calculate the sum of every subarray, and find the maximum one.

func maxSubArray(nums []int) int {
	maxSum := nums[0]

	sumOfArray := func(array []int) int {
		sum := 0
		for _, n := range array {
			sum += n
		}
		return sum
	}

	for i := 0; i < len(nums); i++ {
		for j := 0; j <= i; j++ {
			if sum := sumOfArray(nums[j : i+1]); sum > maxSum {
				maxSum = sum
			}
		}
	}

	return maxSum
}

Subarray that ends at i <-- O(n²)

In previous attempt, we can see the for j := 0; ... loop actually calculated all subarrays that ends at i, I.E. we calculated nums[0 : i + 1], nums[1 : i + 1], nums[2 : i + 1] ..., nums[i : i + 1]. If we calculate them in reverse order, we can utilize previous result to calculate the current one, thus we can turn that O(n²) loop into an O(n) one, and in doing so we make the whole algorithm O(n²).

func maxSubArray(nums []int) int {
	maxSum := nums[0]

	for i := 0; i < len(nums); i++ {
		maxEndsAtCurrent := nums[i]

		sum := nums[i]
		for j := i - 1; j >= 0; j-- {
			sum += nums[j]
			if sum > maxEndsAtCurrent {
				maxEndsAtCurrent = sum
			}
		}

		if maxEndsAtCurrent > maxSum {
			maxSum = maxEndsAtCurrent
		}
	}

	return maxSum
}

Transition between maxEndsAt[i-1] and maxEndsAt[i] <-- O(n)

If we keep maxEndsAtCurrent of each loop in an array, then we can spot that we can actually calculate maxEndsAt[i] based on maxEndsAt[i-1]. Here is the transition function between maxEndsAt[i] and maxEndsAt[i-1]:

	if maxEndsAt[i-1] > 0 {
		maxEndsAt[i] = maxEndsAt[i-1] + nums[i]
	} else {
		maxEndsAt[i] = nums[i]
	}

And we can make the solution O(n):

func maxSubArray(nums []int) int {
	maxEndsAt := make([]int, len(nums))
	maxEndsAt[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		if maxEndsAt[i-1] > 0 {
			maxEndsAt[i] = maxEndsAt[i-1] + nums[i]
		} else {
			maxEndsAt[i] = nums[i]
		}
	}

	maxSum := maxEndsAt[0]
	for i := 1; i < len(maxEndsAt); i++ {
		if maxEndsAt[i] > maxSum {
			maxSum = maxEndsAt[i]
		}
	}
	return maxSum
}

No need to use so much extra space <-- O(n)

Based on the transition function, it looks like only the latest element of maxEndsAt is being used, thus we can get rid of the array and just use one extra variable:

func maxSubArray(nums []int) int {
	maxSum := nums[0] // We can use sum of any sub-array to initialize maxSum here

	var maxEndsAtCurrent int
	for _, n := range nums {
		if maxEndsAtCurrent > 0 {
			maxEndsAtCurrent = maxEndsAtCurrent + n
		} else {
			maxEndsAtCurrent = n
		}

		if maxEndsAtCurrent > maxSum {
			maxSum = maxEndsAtCurrent
		}
	}

	return maxSum
}

Make code even shorter <-- O(n)

There is a builtin max function starting from Go 1.21. By using that function, the transition function can actually be written as:

maxEndsAtCurrent = nums[i] + max(maxEndsAtCurrent, 0)

The final code:

func maxSubArray(nums []int) int {
	maxSum := nums[0] // We can use sum of any sub-array to initialize maxSum here
	var maxEndsAtCurrent int
	for _, n := range nums {
		maxEndsAtCurrent = n + max(maxEndsAtCurrent, 0)
		maxSum = max(maxSum, maxEndsAtCurrent)
	}
	return maxSum
}

Further Reading

If you're interested, you can read Programming Pearls to learn some history behind it.