第三十三天啦
回到上海绢涡，逐步找回節(jié)奏中
終于刷到了一道動態(tài)規(guī)劃的題目
https://leetcode-cn.com/problems/maximum-subarray/
動態(tài)規(guī)劃的題目蹦狂，只要找到“遞推公式”就好弄了
用一個數(shù)組名為dp來保存每個子序列最大和的值祠饺。那么對于第一個元素來說冯吓，他的子序列的值就是自己窟蓝。
那么下一個子序列的值挠阁，就是前一個子序列值最大的和與當(dāng)前值計算一下乱灵，如果前一個子序列值最大的和是負數(shù)踢故，那么這個子序列的值就只能是當(dāng)前的值文黎，如果前一個子序列的值的和是正數(shù)，那么就加上就好
dp[i] = nums[i] + dp[i-1] > 0 ? dp[i-1] : 0
好吧殿较，還是習(xí)慣了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
