Leetcode-53.Maximum Subarray

Posted on | | 阅读数
Words count in article: 112 | Reading time ≈ 1

Question

Solution 1

看到的牛逼解法，在下认输。

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

Solution 2

思路：如果连续的两个元素相加的和小于第二个元素，那么就抛弃第一个元素。

1
2
3
4
5
6
7
8
9
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        temp = result = nums[0]
        for elem in nums[1:]:
            temp += elem
            temp = max(temp, elem)
            if temp > result:
                result = temp
        return result