[파이썬] 리트코드 53. Maximum Subarray 풀이

Maximum Subarray - LeetCode

nums이 주어졌을 때, 연속된 배열의 합이 가장 큰 경우의 합을 출력하는 문제다.

각각의 배열에 대해 모든 합을 계산하는 브루트 포스 방식으로는 풀 수 없다. 조금 더 효율적인 다이나믹 프로그래밍을 이용해야 한다. 

 

nums = [-2,1,-3,4,-1,2,1,-5,4]으로 주어진다면 

포인터를 이동시키면서 배열의 합이나 포인터가 가르키는 숫자 중 큰 것을 cur_mx에 저장해주고

cur_mx와 이전 mx 값 중 최대값을 mx로 갱신하는 식으로 풀었다. 

 

즉, 포인터가 i에 있다면

1. i이전의 값들의 합이 저장된 cur_mx와 포인터가 가르키는 수인 nums[i]를 비교하여 

2. 만약 nums[i]가 더 크다면 현재까지의 최대값(cur_mx)은 nums[i]가 된다 

3. else: 최대값은 이전의 값들이 저장된 cur_mx 그대로다 

4. cur_mx의 최대값을 mx에 저장해준다

 

cur_mx, mx의 초기값은 음의 무한대로 설정했다. 0이라든지 -100000같은 수로 선언하면, 극단적인 테스트 케이스가 나왔을 때 틀릴 수 있기 때문이다. 

 

변수들의 변화를 표로 나타내면 다음과 같다.

num	-2	1	-3	4	-1	2	1	-5	4
cur_mx	-2	1	-2	4	3	5	6	1	5
mx	-2	1	1	4	4	5	6	6	6

class Solution:    
    def maxSubArray(self, nums: List[int]) -> int:
        mx = float('-inf')
        cur_mx = float('-inf')
        for num in nums:
            cur_mx = max(num, cur_mx + num)
            mx = max(mx, cur_mx)
        return mx