[Leetcode] Maximum Subarray - DP

1. 문제

https://leetcode.com/problems/maximum-subarray/description/

 

2. 풀이

 

오늘은 DP 공부를 하면서 배낭문제나, 피보나치로 타뷸레이션/메모이제이션을 공부했다.

 

개중에 처음으로 배운 'Kadane's Algorithm'을 배우게 되어서 남긴다!

 

카데인 알고리즘은 하나의 배열에서 연속된 부분합의 최대를 구할때 용이하다.

 

 

1) 카데인 알고리즘 적용

1-1) 현재 max, 전체 max 변수를 설정한다.

1-2) nums[0]을 각각 최대값 저장 변수에 할당해줬다면, 이제 그 뒤로 얘를 더하는게 클지, 안더하고 다음 nums[i] 자체가 클지 판단한다.

1-3) 현재max / 전체max 중 무엇인가가 더 클 것이고, 그럼 이 curr_max를 best_max랑 비교해서 또 저장한다.

 

## code ##

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        # 카데인 알고리즘 적용 - O(n): 연속합 찾기
        max_sum = curr_sum = nums[0]

        for num in nums[1:]:
            curr_sum = max(num, curr_sum + num)
            max_sum = max(max_sum, curr_sum)
        return max_sum

 

 

2) 메모이제이션 적용

솔직히 위 방법과 유사하다. 뭐 다른 방식을 썻다,, 할 수 있긴한데 그게 그거인듯

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

 

2-1)  nums[i] 에다가 num[i-1]이 0보다 크면 (양수라서 더하면 더 커질 수 있다면) 더하고 아니면 안한다!

 

이건 한줄로 끝날거같당

 

둘다 O(n)이라서 속도가 아주 빠르다!