Kadane's Algorithm

LeetCode 53 · View on LeetCode

Find the contiguous subarray with the largest sum. At each index, either extend the current subarray or start fresh — if the running sum is negative, it can only hurt.

package main

import "fmt"

func maxSubArray(nums []int) int {
	maxSum := nums[0]
	curSum := nums[0]
	for i := 1; i < len(nums); i++ {
		if curSum+nums[i] > nums[i] {
			curSum += nums[i]
		} else {
			curSum = nums[i]
		}
		if curSum > maxSum {
			maxSum = curSum
		}
	}
	return maxSum
}

func main() {
	fmt.Println(maxSubArray([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4})) // 6
	fmt.Println(maxSubArray([]int{1}))                               // 1
	fmt.Println(maxSubArray([]int{-1, -2, -3}))                      // -1
}