返回一个数组中,子数组最大累加和。
动态规划。这道题过于经典,就不说具体过程了。时间复杂度:O(N)。空间复杂度:O(1)。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
arr := []int{-1, 2, 3, 4}
ret := maxSubArray2(arr)
fmt.Println(ret)
}
func maxSubArray2(arr []int) int {
if len(arr) == 0 {
return 0
}
N := len(arr)
ans := arr[0]
pre := arr[0]
for i := 1; i < N; i++ {
pre = getMax(arr[i], pre+arr[i])
ans = getMax(ans, pre)
}
return ans
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下: