2021-06-14：返回一个数组中，子数组最大累加和。

福大大架构师每日一题

发布于 2021-08-05 16:00:50

4020

发布于 2021-08-05 16:00:50

文章被收录于专栏：福大大架构师每日一题

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
    }
}

执行结果如下：