描述

输入一个长度为 n 的整型数组 array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围:

• 1<=n<=2×105
• −100<=a[i]<=100

要求：时间复杂度为 O(n)，空间复杂度为 O(n)

进阶：时间复杂度为 O(n)，空间复杂度为 O(1)

示例

// 输入
[1,-2,3,10,-4,7,2,-5]
// 输出：输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
18

// 输入
[2]
// 输出
2

// 输入
[-10]
// 输出
10

解题思路

动态规划

代码实现

/**
 * [JZ44-简单] 数字序列中某一位的数字
 *
 * @param array int 一维数组
 * @return int
 */
func findGreatestSumOfSubArray(array []int) int {
    length := len(array)
    if 1 == length {
        return array[0]
    }

    dp := make([]int, length)
    dp[0] = array[0]
    max := array[0]
    for i := 1; i < length; i++ {
        dp[i] = int(math.Max(float64(dp[i-1]+array[i]), float64(array[i])))
        max = int(math.Max(float64(dp[i]), float64(max)))
    }
    return max
}