LeetCode 53. Maximum Subarray

파이썬 알고리즘 인터뷰 86번(리트코드 53번) Maximum Subarray
https://leetcode.com/problems/maximum-subarray/

나의 풀이

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        left = right = 0
        curr = M = nums[0]

        while right < len(nums):
            if curr < 0:
                right += 1
                left = right
                if right < len(nums):
                    curr = nums[left]
            else:
                right += 1
                if right < len(nums):
                    curr += nums[right]
            M = max(M, curr)

        return M
            

다른 풀이1

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)

다른 풀이2(Kadane’s Algorithm)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        cur_sum , max_sum = nums[0], nums[0]
        # nums = [-2, 1, -3, 4,-1,2,1,-5, 4]
        for num in nums[1:]:
            cur_sum = max(num, cur_sum + num) # -2, 1, -2, 4, 3, 5, 6, 1, 5
            max_sum = max(max_sum, cur_sum)   # -2, 1,  1, 4, 4, 5, 6, 6, 6

        return max_sum