第三十三天 Maximum Subarray

第三十三天啦

回到上海，逐步找回节奏中

终于刷到了一道动态规划的题目

https://leetcode-cn.com/problems/maximum-subarray/

动态规划的题目，只要找到“递推公式”就好弄了

用一个数组名为dp来保存每个子序列最大和的值。那么对于第一个元素来说，他的子序列的值就是自己。
那么下一个子序列的值，就是前一个子序列值最大的和与当前值计算一下，如果前一个子序列值最大的和是负数，那么这个子序列的值就只能是当前的值，如果前一个子序列的值的和是正数，那么就加上就好

dp[i] = nums[i] + dp[i-1] > 0 ? dp[i-1] : 0

好吧，还是习惯了Java的三元运算符的写法。

有了递推公式的话，那么代码就很简单了

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 1:
            return 0
        ret = nums[0]
        dp = []
        dp.append(nums[0])
        for i in range(1,len(nums)):
            if dp[i-1] < 0:
                dp.append(nums[i])
            else:
                dp.append(nums[i] + dp[-1])
            if ret < dp[i]:
                ret = dp[i]
        return ret