思路分析

本题的常规解题路线有3种:

1. 暴力枚举，优化后时间复杂度为$O(n^2)$
2. 分治，分别考虑字串在左边、字串在中间、字串在右边三种情况，时间复杂度为$O(nlog n)$
3. 动态规划，也就是本题要讲的一种方法，时间复杂度为$O(n)$

常规解法很容易想到，也很容易做出来，但是由于需要两个for循环嵌套，所以其时间复杂度为$O(n^2)$，不满足本题的要求。故本题使用动态规划法。

输入三个变量

l = len(nums) # 数组长度，用于后续遍历使用
s = max(nums) # 和为数组最大值，最大值的目的是防止数组元素全负导致出0
b = 0 # 初始化变量

开始遍历

对b进行判断

• 如果b>0：说明当前这个子串有可能是最大的，那就继续加上第i项；
• 如果b<=0：说明当前这个字串和为负，那就没有比较的意义了，将b初始化为第i项
• 最后判断b>s?
• 如果b大于s，则更新s的值为b

最后输出s的结果即可

代码实现

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = len(nums)
        s, b = max(nums), 0
        for i in range(0, l):
            if b > 0:
                b += nums[i]
            else:
                b = nums[i]
            if b > s:
                s = b
        return s