정수 배열 A가 주어졌을 때, 길이가 1 이상인 연속된 부분 배열(contiguous subarray) 중에서 원소의 합이 가장 큰 구간을 찾고, 그 합을 반환하는 문제입니다.
예를 들어 배열이 A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]라고 한다면, 합이 가장 큰 부분 배열은 [4, -1, 2, 1]이며 그 합은 6입니다.
동적 계획법(Dynamic Programming) 접근 방식
이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열 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])에 현재 원소를 더해서 이어가는 것이 유리한지, 아니면 현재 원소부터 새로운 구간을 시작하는 것이 유리한지를 매번 비교하는 것입니다. 이 방식은 널리 알려진 카데인 알고리즘(Kadane's Algorithm)과 동일한 원리입니다.
예제 코드 (Python)
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
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.maxSubArray(nums))입력
nums = [-2, 1, -3, 7, -2, 2, 1, -5, 4]
출력
8
위 예제에서 최대 합은 8이며, 이는 부분 배열 [7, -2, 2, 1]의 합입니다.
시간 복잡도와 공간 최적화
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 또한 dp 배열 전체를 저장할 필요 없이 직전 값 하나만 기억하면 되므로, 공간 복잡도를 O(1)로 줄일 수도 있습니다.
def maxSubArray(self, nums):
current_sum = best_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
best_sum = max(best_sum, current_sum)
return best_sum두 변수 current_sum(현재 위치까지의 최대 합)과 best_sum(전체 최대 합)만 갱신하면서 진행하기 때문에 메모리 사용량이 훨씬 적습니다. 실무나 코딩 인터뷰에서는 이 최적화된 버전을 사용하는 것이 좋습니다.