53.-maximum-subarray.md

53. Maximum Subarray

{% tabs %} {% tab title="Go" %}

func maxSubArray(nums []int) int {
    if len(nums)==0 {
        return 0
    } else if len(nums) == 1 {
        return nums[0]
    }else {
        var ans int
        var cur int
        ans = nums[0]
        cur = nums[0]
        for i:=1; i < len(nums); i++ {
            cur = max(nums[i], nums[i] + cur)
            ans = max(ans,cur)
        }
        return ans 
    }
    
}

func max(a int,b int)int {
    if a > b {
        return a
    } else {
        return b
    }
}

{% endtab %}

{% tab title="Python" %}

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        
        ## 排除conern case 以后
        ans = cur = nums[0]
        
        for i in range(1,len(nums)):
            cur = max(nums[i],cur + nums[i]) ## 要不从新数起,要不一直累计 
            ans = max(ans,cur)
        return ans

{% endtab %} {% endtabs %}