动态规划大法。

第一步，建模,得出递推公式

有一个数组A[n], 对于A[i] (0<i<n)位置向前（0位置方向）最大和为C[i], 那么

C[i] = Max(C[i-1] + A[i], A[i])

终止条件

C[0] = A[0]

这样子我们就得到了对于任意一个位置 0 <= i < n，数组中从0到i的最大子串和。

但是我们的目标并不是求i位置，最大子串和。我们的目标是求整个数组上，最大子串和，也就是

Opt(A) = Max(C[i]), 0 <= i < n

第二步，试着实现算法

class Solution:
    def maxSubArray(self, nums):
        # write your code here
        length = len(nums)
        c = [0] * length
        c[0] = nums[0]
        maxSum = c[0]

        i = 1
        while i < length:
            if c[i-1] + nums[i] > nums[i]:
                c[i] = c[i-1] + nums[i]
            else:
                c[i] = nums[i]
            if c[i] > maxSum:
                maxSum = c[i]

            i += 1

        return maxSum

代码优化：

1. 化简判断条件

2. 我们求解C[i]只需要C[i-1], 所以我们并不需要存下所有的C[i]。我们只需要一个变量prev存储C[i-1]的值即可达到目的。
   所以代码可以经简称这样

   class Solution:
   def maxSubArray(self, nums):
       length = len(nums)
       maxSum = nums[0]
       prev = maxSum
   
       i = 1
       while i < length:
           if prev + nums[i] > nums[i]:
               prev = prev + nums[i]
           else:
               prev = nums[i]
   
           if prev > maxSum:
               maxSum = prev
   
           i += 1
   
       return maxSum

进一步优化，其实我们也不需要每次都用nums[i]去访问元素，因为这样可能会多一步寻址操作。我们改用for in

class Solution:
    def maxSubArray(self, nums):
        if len(nums) == 0:
            return None

        maxSum = nums.pop(0)    # 最大值为0号元素
        prev = maxSum           # 设置初始条件C[0] = A[0]

        for num in nums:
            # current = max(prev + num, num)
            current = prev + num    
            if current < num:
                current = num

            # update max sum
            if current > maxSum:
                maxSum = current

            prev = current

        return maxSum

算法复杂度O(n)