배열 A가 주어졌을 때, 합이 최대가 되는 연속된 부분 배열(contiguous subarray)을 찾고 그 합을 반환하는 문제입니다. 예를 들어 배열 A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]라면, 최대 합은 6이며, 이때의 부분 배열은 [4, -1, 2, 1]입니다.
이 문제는 동적 프로그래밍(Dynamic Programming) 기법으로 효율적으로 해결할 수 있으며, 널리 알려진 카데인 알고리즘(Kadane's Algorithm)이 바로 이 방식에 기반합니다.
알고리즘 접근 방식
핵심 아이디어는 각 위치에서 "이전까지의 누적 합에 현재 원소를 더할 것인가, 아니면 현재 원소부터 새로 시작할 것인가"를 판단하는 것입니다.
- A와 같은 크기의 dp 배열을 정의하고 0으로 초기화합니다
- dp[0] := A[0] 으로 설정합니다
- i를 1부터 (A의 길이 - 1)까지 반복하며 다음을 수행합니다
- dp[i] := max(dp[i-1] + A[i], A[i])
- 마지막으로 dp 배열의 최대값을 반환합니다
dp[i]는 "i번째 원소를 마지막으로 하는 부분 배열의 최대 합"을 의미합니다. 만약 이전 누적 합(dp[i-1])이 음수라면, 이를 더하는 것보다 현재 원소부터 새로 시작하는 것이 유리하기 때문입니다.
구현 예제
다음은 파이썬으로 작성한 전체 코드입니다.
class Solution(object): def solve(self, nums): dp = [0 for i in range(len(nums))] dp[0] = nums[0] for i in range(1,len(nums)): dp[i] = max(dp[i-1]+nums[i],nums[i]) return max(dp) nums = [-2,1,-3,7,-2,2,1,-5,4] ob1 = Solution() print(ob1.solve(nums))
입력
[-2,1,-3,7,-2,2,1,-5,4]
출력
8
동작 과정 살펴보기
입력 배열 [-2, 1, -3, 7, -2, 2, 1, -5, 4]에 대해 각 인덱스의 dp 값은 다음과 같이 계산됩니다.
- dp[0] = -2 → 시작점
- dp[1] = max(-2+1, 1) = 1 → 새로 시작하는 것이 유리
- dp[2] = max(1-3, -3) = -2
- dp[3] = max(-2+7, 7) = 7 → 새로 시작
- dp[4] = max(7-2, -2) = 5
- dp[5] = max(5+2, 2) = 7
- dp[6] = max(7+1, 1) = 8 ← 최대값
- dp[7] = max(8-5, -5) = 3
- dp[8] = max(3+4, 4) = 7
따라서 결과는 8이며, 이는 부분 배열 [7, -2, 2, 1]의 합과 일치합니다.
시간 복잡도
위 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가로 사용되는 공간은 O(n)입니다. 실제로는 dp 배열 없이 현재 누적 합과 전체 최대값 두 개의 변수만 사용하여 공간 복잡도를 O(1)로 줄일 수도 있습니다.