53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/description/
题意：求最大连续子段和
思路：DP

摘自《计算机算法设计与分析》王晓东 第3版

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum = nums[0]  #初始累加和
        b = nums[0]  #dp初始状态，0号
        for i in range(1, len(nums)):  #从1号开始
            if b > 0:
                b += nums[i]
            else:
                b = nums[i]
            sum = max(b, sum)
        return sum