LeetCode 53 - Maximum Subarray

이 문제는 정수 배열에서 합이 가장 큰 연속 부분 배열을 찾아 그 합을 반환하는 Medium 난이도 문제다. 한동안 풀이를 고민했지만 전체 구간을 반복해서 계산하지 않는 방법을 찾지 못했고, 힌트를 확인한 뒤 Kadane 알고리즘의 기준을 코드로 옮겼다. 분명 예전에 풀었던 기록이 있는데 왜 기억이 나지 않는지 ㅎㅎ

문제 링크 & 설명

문제 링크: 53. Maximum Subarray
요약: 정수 배열 nums에서 원소가 하나 이상인 연속 부분 배열 가운데 합이 가장 큰 경우의 합을 반환하는 문제.

예를 들어 다음 배열이 주어진다.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

합이 가장 큰 연속 구간은 [4, -1, 2, 1]이고 결과는 6이다. 원소를 골라서 조합하는 문제가 아니라 배열에서 끊기지 않은 구간을 선택해야 한다.

모든 시작점에서 끝점을 늘려가며 합을 계산하면 답은 구할 수 있지만, 구간 수가 많아져 시간 복잡도가 O(n²)까지 증가한다. 이번 풀이에서는 현재 위치에서 끝나는 최대 합만 유지하면서 배열을 한 번 순회했다.

접근 방법

현재 숫자부터 다시 시작할지 결정하기

배열의 i번째 숫자까지 왔을 때 필요한 선택지는 두 가지다.

이전 구간의 합에 현재 숫자를 이어 붙인다.
현재 숫자부터 새로운 구간을 시작한다.

이전 위치에서 끝나는 최대 합을 prev_sum이라고 하면, 현재 위치에서 끝나는 최대 합은 다음 식으로 계산할 수 있다.

prev_sum = max(prev_sum + nums[i], nums[i])

판단 기준은 prev_sum의 부호를 따로 검사하는 것이 아니라, prev_sum + nums[i]와 nums[i]를 직접 비교하는 것이다. 앞의 값이 더 크면 이전 구간에 현재 숫자를 이어 붙이고, 뒤의 값이 더 크면 이전 구간을 버린 뒤 현재 숫자부터 새로 시작한다.

prev_sum에는 현재 인덱스에서 끝나는 연속 부분 배열의 최대 합을 저장한다.

전체 최대 합을 따로 기록하기

현재 위치에서 끝나는 최대 합을 구했더라도 전체 정답은 앞쪽 인덱스에서 이미 나왔을 수 있어서, 각 반복에서 max_sum을 별도로 갱신한다.

max_sum = max(max_sum, prev_sum)

예제의 일부를 따라가면 값이 이렇게 변한다.

현재 값     prev_sum     max_sum
  -2           -2          -2
   1            1           1
  -3           -2           1
   4            4           4
  -1            3           4
   2            5           5
   1            6           6

-3까지 더한 합은 다음 숫자 4에 도움이 되지 않으므로 4에서 새 구간을 시작한다. 이후 -1은 합을 줄이지만, 뒤의 2와 1까지 연결했을 때 전체 합이 6이 되므로 구간 안에 남는다.

트러블 슈팅

처음에는 연속 부분 배열의 범위를 어떻게 정해야 할지 몰라서 선형 시간 풀이를 만들지 못했다. 구간의 시작점과 끝점을 모두 관리하려고 하면 가능한 범위를 계속 비교해야 하는데, 합만 반환하는 이 문제에서는 실제 인덱스를 저장할 필요가 없었다.

Kadane 알고리즘은 현재 위치에서 끝나는 최대 합이라는 상태 하나로 비교 범위를 줄인다. 이전 구간을 이어갈지 현재 값부터 다시 시작할지만 결정하면 되고, 그 결과 가운데 가장 큰 값을 별도로 보관하면 전체 답을 얻을 수 있다.

초깃값을 0으로 두지 않은 이유도 확인했다.

prev_sum = nums[0]
max_sum = nums[0]

nums가 [-3, -2, -5]처럼 모두 음수라면 정답은 -2다. max_sum을 0으로 시작하면 배열에 존재하지 않는 빈 구간을 선택한 결과가 되므로, 첫 번째 원소로 두 값을 초기화하고 두 번째 원소부터 순회해야 한다.

복잡도 분석

시간 복잡도: O(n)
- 배열의 각 원소를 한 번씩 확인하며, 반복마다 상수 시간의 비교와 덧셈만 수행한다.
공간 복잡도: O(1)
- 배열 크기와 관계없이 prev_sum과 max_sum 등 몇 개의 변수만 사용한다.

구현 코드

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]

        prev_sum = nums[0]
        max_sum = prev_sum

        for i in range(1, n):
            prev_sum = max(prev_sum + nums[i], nums[i])
            max_sum = max(max_sum, prev_sum)

        return max_sum

요약 및 회고

이 문제에서 prev_sum의 정의는 현재 인덱스에서 끝나는 연속 부분 배열의 최대 합이다. 이 상태를 유지하면 이전 구간을 이어갈지 현재 숫자에서 새로 시작할지를 한 번의 비교로 결정할 수 있고, 별도의 max_sum으로 전체 최댓값을 기록할 수 있다.

모든 구간을 직접 만들지 않아도 되는 이유는 각 위치에서 다음 계산에 필요한 값이 prev_sum 하나이기 때문이다. 현재 문제의 답만 저장하는 것이 아니라, 다음 단계가 사용할 상태를 어떻게 정의할지 먼저 정하는 방식이었다.