[LeetCode] Maximum Subarray 파이썬 (dp, local max, global max)

dp 사용

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [num for num in nums]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1]+nums[i], nums[i])
        return max(dp)

 

dp 미사용

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 3/26/2021 microsoft prep
        max_sub = 0
        global_max = float('-inf') 
        for n in nums:
            max_sub = max(max_sub + n, n)
            global_max = max(max_sub, global_max)
        return global_max