nums라는 배열이 주어졌을 때, 부분 배열 [nums_l, nums_l+1, ..., nums_r-1, nums_r]의 절대합은 |nums_l + nums_l+1 + ... + nums_r-1 + nums_r|로 정의됩니다. 이때 nums의 모든 부분 배열 중에서 가장 큰 절대합을 찾아야 합니다. 단, 부분 배열은 빈 배열일 수도 있습니다.
문제 예시
예를 들어 입력이 nums = [2,-4,-3,2,-6]이라면 결과는 11입니다. 부분 배열 [2,-4,-3,2]의 절대합 |2 + (-4) + (-3) + 2| = 11이 모든 부분 배열 중 가장 크기 때문입니다.
풀이 전략
이 문제는 유명한 카데인 알고리즘(Kadane's Algorithm)을 응용하면 선형 시간 O(n)에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 최대 절대합은 '최대 부분 배열 합' 또는 '최소 부분 배열 합'의 절댓값 중 하나입니다.
- 첫 번째 루프에서는 누적 합이 음수가 되면 0으로 초기화하며 최대 합을 추적합니다.
- 두 번째 루프에서는 누적 합이 양수가 되면 0으로 초기화하여 최소 합(음수 방향)을 추적합니다.
- 각 단계마다 ans를 ans와 |temp| 중 더 큰 값으로 갱신하고, 마지막에 ans를 반환합니다.
알고리즘 단계
- n := nums의 길이
- ans := 0, temp := 0
- i를 0부터 n-1까지 순회:
- temp < 0이면 temp := 0으로 초기화
- temp := temp + nums[i]
- ans := max(ans, |temp|)
- temp := 0으로 초기화
- i를 0부터 n-1까지 다시 순회:
- temp > 0이면 temp := 0으로 초기화
- temp := temp + nums[i]
- ans := max(ans, |temp|)
- ans 반환
구현 예제
다음 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
def solve(nums):
n = len(nums)
ans = 0
temp = 0
# 최대 부분 배열 합 탐색 (카데인 알고리즘)
for i in range(n):
if temp < 0:
temp = 0
temp += nums[i]
ans = max(ans, abs(temp))
# 최소 부분 배열 합 탐색 (절댓값 기준)
temp = 0
for i in range(n):
if temp > 0:
temp = 0
temp += nums[i]
ans = max(ans, abs(temp))
return ans
nums = [2, -4, -3, 2, -6]
print(solve(nums))입력
[2, -4, -3, 2, -6]
출력
11
정리
이 풀이는 배열을 두 번 순회하지만 각 순회가 O(n)이므로 전체 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다. 최대합과 최소합을 동시에 고려하는 것이 최대 절대합 문제의 핵심 포인트이며, 실제 코딩 테스트에서 자주 등장하는 변형 문제이므로 카데인 알고리즘과 함께 익혀두면 유용합니다.