리트코드 53번 Maximum Subarray (python)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

Solution

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr = max_sum = nums[0]
        for idx, num in enumerate(nums[1:]):
            if curr + num > num:
                curr += num
            else:
                curr = num
            max_sum = max(max_sum, curr)

        return max_sum

subarray가 아닌 최대 합의 값만 구하면 되는 문제이다. 현재까지 합에 현재 num을 더했을 때 num보다 작거나 같다면 현재까지의 합을 num으로 업데이트 하며 풀었다.

카데인 알고리즘 풀이와 비슷하다.

import sys
from typing import List

class Solution:
		def maxSubArray(self, nums:List[int]) -> int:
        best_sum = -sys.maxsize
        current_sum = 0
        for num in nums:
            current_sum = max(current_sum, current_sum + num)
            best_sum = max(best_sum, current_sum)
            
        return best_sum

Reference

파이썬 알고리즘 인터뷰 86번