Python O(n)


  • 0
    A

    ···
    def maxSubArray(self, nums):

        minus_count = 0 #记录负数的个数
        cur_max = max = 0
        length = len(nums)
        if length <= 0:
            return None
        for i in range (length):
            if nums[i] < 0:
                minus_count += 1
            cur_max += nums[i]
            if cur_max > 0:
                if max < cur_max:
                    max = cur_max
            else:
                cur_max = 0
    
        if minus_count == length:#如果全是负数,上面的算法不适用,选一个最小的负数。
            max = nums[0]
            for i in range(length):
                if max < nums[i]:
                    max = nums[i]
        return max
    

    ···


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.