[LeetCode][python3]Day03. Maximum Subarray (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.03

1. My solution

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sub=nums[0]
        cur_sub=nums[0]
        for i in nums[1:]:
            if cur_sub<i and cur_sub<0:
                cur_sub=i
            elif i<0:
                max_sub=max(cur_sub,max_sub)
                cur_sub+=i
            else:
                cur_sub+=i
        max_sub=max(cur_sub,max_sub)
        return max_sub

Explanation:

I don’t know why I’ll make the script logic like this, but this is my first thought of the solution. This is faster then most of the others because they use two max function in every for loop, that slows down the progress.

2. A Common Solution

class Solution:
    def maxSubArray(self, numbers: List[int]) -> int:
        current_sum = numbers[0]
        maximum_sum = numbers[0]
        for number in numbers[1:]:
            current_sum = max(current_sum + number, number)
            maximum_sum = max(maximum_sum, current_sum)
        return maximum_sum

3. A Good Solution

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        length=len(nums)
        if not nums:return None
        if length==1:return nums[0]
        localmax=nums[0]
        globalmax=localmax
        for i in range(1,length):
            if localmax<0:
                localmax=nums[i]
            else:
                localmax=nums[i]+localmax
            if localmax>globalmax:
                globalmax=localmax
        return globalmax