剑指 Offer 42. 连续子数组的最大和

题目描述

https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
注意：本题与主站 53 题相同：https://leetcode-cn.com/problems/maximum-subarray/

解题思路

每一个以数组第i位结尾的子数组的和的最大值都取决于它自己以及之前的子数组。因此这个题考虑使用动态规划算法。
状态定义：dp[i]为以元素nums[i]为结尾的连续子数组最大和
转移方程：i>0时，dp[i] = max(dp[i-1] + nums[i], nums[i])
原理：如果之前的那些数造成的贡献（可能为负也可能为小正数） + 我最新的贡献还不如不如我单打独斗的贡献，不如我自己一个人来；否则就使用他们的贡献和我的贡献的和。
初始状态：dp[0] = nums[0]
返回值：max(dp)

解题代码

python

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        # dp[i]为以第i个数结尾时,最大的子数组之和
        dp = []
        dp.append(nums[0])
        for i in range(1, len(nums)):
            dp.append(max(dp[i - 1] + nums[i], nums[i]))
        return max(dp)

golang

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

func maxInSlice(s []int) int {
    maxNum := s[0]
    for _, v := range s[1:] {
        if v > maxNum {
            maxNum = v
        }
    }
    return maxNum
}

func maxSubArray(nums []int) int {
    var dp []int = []int{nums[0]}
    for i := 1; i < len(nums); i++ {
        dp = append(dp, max(nums[i], (dp[i-1]+nums[i])))
    }
    return maxInSlice(dp)
}

执行结果

执行结果：通过
执行用时：80 ms, 在所有 Python3 提交中击败了41.83%的用户
内存消耗：21 MB, 在所有 Python3 提交中击败了10.53%的用户