题目描述

我的解法

O(n)的复杂度，sum[i]=max{sum[i-1] + a[i], a[i]}

class Solution:
    def maxSubArray(self, nums):
        sums=nums[0]
        s=0
        for i in range(len(nums)):
            if s > 0:
                s=s+nums[i]
            else:
                s=nums[i]
            if sums < s:
                sums=s
        return sums

最优解法

class Solution:
    def maxSubArray(self, nums):
        sum = 0
        max = nums[0]
        
        for index in range(len(nums)):
            if sum < 0:
                sum = 0

            sum += nums[index]
            
            if sum > max:
                max = sum
        
        return max