最大子序和

题目

给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路

一、动态规划

考虑当前位置i，能组成的最大子序和dp[i]与dp[i - 1]有关。
如果dp[i - 1] > 0 , 则dp[i] = nums[i] + dp[i - 1]
否则，dp[i] = nums[i]。

二、分治

• todo

代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        if len(nums) == 1: return nums[0]
        dp = nums[:]
        for i in range(1, len(nums)):
            if dp[i - 1] > 0:
                dp[i] = nums[i] + dp[i - 1]
        return max(dp)

优化一下，不需要dp_table，只需要两个变量就行。
一个localMax保存局部最大的子序和，一个globalMax保存全局最大的子序和。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        localMax, globalMax = nums[0], nums[0]
        for num in nums[1:]:
            if localMax <= 0:
                localMax = num
            else:
                localMax += num
            globalMax = max(globalMax, localMax)
            # print(globalMax)
        return globalMax