2021-06-14:返回一个数组中,子数组最大累加和。
福大大 答案2021-06-14:
动态规划。这道题过于经典,就不说具体过程了。时间复杂度: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
}
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class04/Code02_SubArrayMaxSum.java)