Easy, Dynamic Programming

給定序列（至少包含一個(gè)數(shù)），尋找連續(xù)子序列，其擁有最大和。

Example, 給定 [-2,1,-3,4,-1,2,1,-5,4],
最大子序列[4,-1,2,1] 最大和 6.

這是一個(gè)dynamic programming 解決的優(yōu)化問(wèn)題。求A[:]的子序列最大和可以轉(zhuǎn)為求A[:i]的子序列最大和，i為子序列的最大值，不斷更行子問(wèn)題的解來(lái)求得最終解。也可以說(shuō)是使用了divide and conqure 的思想。

如果已知A[:i-1]的子序列最大和sum(i-1)，那A[:i]的解就是取sum(i-1)和i位置的局部最大值的較大值。那么如何求i位置的局部最大值，同樣也是一個(gè)DP問(wèn)題，對(duì)i-1位置的局部最大值進(jìn)行更新。

此題對(duì)于沒(méi)有DP思想的coder來(lái)說(shuō)其實(shí)是很難的一道題，但是LeetCode將其分類為easy。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        localmax, globalmax = 0, None
        for num in nums:
            globalmax = max(globalmax, localmax+num)
            localmax = max(0, localmax+num)
        return globalmax