Login light

超时解法

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxResult = nums[0]
        for i in range(len(nums)):
            for o in range(i, len(nums) + 1):
                if len(nums[i:o]) > 0 and sum(nums[i:o]) > maxResult:
                    maxResult = sum(nums[i:o])
        return maxResult

动态规划:O(n) (手弟)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        retSum = nums[0]
        mSum = 0
        for num in nums:
            if num + mSum < 0:
                mSum = 0
                if retSum < num:
                    retSum = num
            else:
                mSum += num
                if retSum < mSum:
                    retSum = mSum
        return retSum

动态规划:O(n) (andy)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        retSum = nums[0]
        mSum = 0
        for num in nums:
            if mSum < 0:
                mSum = num
            else:
                mSum += num
            retSum = max(mSum, retSum)
        return retSum