跳转至

LC53 - 最大子数组和

MaximumSubarray.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
package Array

import "math"

func maxSubArray(nums []int) int {
    nums = append([]int{0}, nums...)
    prefixSum := make([]int, len(nums))
    for i := 1; i < len(nums); i++ {
        prefixSum[i] = prefixSum[i-1] + nums[i]
    }
    minPrefixSum := 0
    maxSum := math.MinInt
    for i := 1; i < len(nums); i++ {
        maxSum = max(maxSum, prefixSum[i]-minPrefixSum)
        minPrefixSum = min(minPrefixSum, prefixSum[i])
    }
    return maxSum
}

前缀和