leetcode

Maximum Subarray

Maximum Subarray

one solution - 24ms

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)

another solution - 44ms

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        cur_sum = max_sum = nums[0]
        for num in nums[1:]:
            cur_sum = max(num, cur_sum + num)
            max_sum = max(max_sum, cur_sum)
        return max_sum

test code

1
2
3
4
In [470]: s = Solution(); t = s.maxSubArray([-2,1,-3,4,-1,2,1,-5,4])
In [471]: t
Out[471]: 6

leet code