題目

給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。
進階:

如果你已經(jīng)實現(xiàn)復雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-subarray
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

解題思路

• 當所有都小于0，直接返回最大值
• 當新加入一個數(shù)，local_max如果小于0， 更新為0； 否則為local_max
• 當新加入當數(shù)為負，local_max會變小，否則會變大； 更新global_max

最大子串肯定是從正數(shù)開始計算，只要保證前面計算出來的值是正的，就能讓后面的計算增大。在這個過程中不算保存最大的值。

代碼

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if max(nums) < 0:
            return max(nums)
        
        local_max, global_max = 0,0
        
        for v in nums:
            local_max = max(0, local_max+v)
            global_max = max(local_max, global_max)
        
        return global_max