53. Maximum Subarray 풀이

leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

# Greedy
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        if not nums :
            return 0
        
        curr_max = output = nums[0]
        
        for i in range(1, len(nums)) :
            curr_max = max(curr_max+nums[i], nums[i])          
            output = max(output, curr_max)
        
        return output
            
# DP
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        if not nums :
            return 0
        
        n, output = len(nums), nums[0]
        dp = [0]*(n+1)
        
        for i in range(n) :
            dp[i] = max(nums[i], dp[i-1]+nums[i])
            output = max(dp[i], output)
            
        return output
        

정리 : 

*contiguous* 라는 조건이 있다.

이를 잘 활용해서 생각해보면 이전까지 더한 값이 음수면 굳이 현재 subarray에 이 값을 더할 이유가 전혀 없다.