Maximum Subarray

Medium

The problem

Given a slice of integers (which may be negative), find the contiguous part (at least one element) with the largest sum, and return that sum.

Example 1
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
The part [4, -1, 2, 1] adds up to 6, and no other part beats it.
Example 2
Input: nums = [5, 4, -1, 7, 8]
Output: 23
Taking the whole slice gives 23.
Example 3
Input: nums = [-3, -1, -2]
Output: -1
Every number is negative, so the best you can do is the single element -1.

Limits

1 ≤ len(nums) ≤ 100,000
-10,000 ≤ nums[i] ≤ 10,000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

If the running sum before the current number is negative, is it helping or hurting?

The idea

Kadane: curr = max(num, curr + num); best = max(best, curr).

Target: O(n) time, O(1) space

Go function shape

func maxSubArray(nums []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// MaxSubArray (Kadane): if the running sum before this number is negative it only hurts, so drop it and
// start fresh here. cur = the best sum of a subarray that ENDS at this number.
func MaxSubArray(nums []int) int {
	best, cur := nums[0], 0
	for _, n := range nums {
		cur = max(n, cur+n)
		best = max(best, cur)
	}
	return best
}

Read the lesson: Greedy