问题

找出数组nums中的一个连续子数组，它们的和最大。

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路

用dp[i]表示以index i结尾的连续子数组的最大和。这个值取决于dp[i-1]和nums[i]，如果dp[i-1]+nums[i]的值要大于dp[i-1]，就继续沿用dp[i-1]中选择的子数组继续延伸，否则就以nums[i]开头定义新的子数组。

dp公式为：\(dp[i] = max(nums[i], dp[i-1] + nums[i])\)。最后对dp数组取最大的数即可。

因为dp只取决于前一个数，可以优化，省去dp的数组空间开销。

时间复杂度O(n)，空间复杂度O(1)

代码

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxSum = dp = nums[0]
        for i in range(1,len(nums)):
            dp = max(nums[i], dp+nums[i])
            if(dp>maxSum):
                maxSum = dp
        return maxSum
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄