문제 정의
정수 배열 A로 표현되는 원형 배열(circular array) C가 주어졌다고 가정해 보겠습니다. 목표는 C에서 비어 있지 않은 부분배열(subarray) 중 합이 최대가 되는 값을 찾는 것입니다. 단, 하나의 부분배열은 고정 버퍼 A의 각 원소를 최대 한 번만 포함할 수 있습니다.
예를 들어 배열이 [1, -2, 3, -2]라면 결과는 3입니다. 부분배열 [3]의 합이 3으로 가장 크기 때문입니다.
풀이 전략
원형 배열에서 최대 합 부분배열은 다음 두 가지 경우 중 하나에 해당합니다.
- 경계를 넘지 않는 경우 — 일반적인 선형 배열과 동일하므로 카데인 알고리즘(Kadane's algorithm)으로 해결할 수 있습니다.
- 경계를 넘는 순환 구간의 경우 — 배열의 뒷부분과 앞부분이 이어진 구간이므로, 왼쪽 누적 합(prefix sum)과 오른쪽 누적 합을 조합하여 계산합니다.
최종 정답은 두 경우 중 더 큰 값이 됩니다.
알고리즘 단계
n := 배열 v의 크기
크기 n의 배열 leftSum, leftSumMax, rightSum, rightSumMax를 생성합니다.
leftSum[0] := v[0], leftSumMax[0] := max(0, v[0])
i를 1부터 n-1까지 반복:
leftSum[i] := leftSum[i-1] + v[i]
leftSumMax[i] := max(leftSum[i], leftSumMax[i-1])rightSum[n-1] := v[n-1], rightSumMax[n-1] := max(0, v[n-1])
i를 n-2부터 0까지 역방향으로 반복:
rightSum[i] := rightSum[i+1] + v[i]
rightSumMax[i] := max(rightSumMax[i+1], rightSum[i])leftAns := leftSum[0] + rightSumMax[1]
i를 1부터 n-2까지 반복하며 leftAns := max(leftAns, leftSum[i] + rightSumMax[i+1])로 갱신
rightAns := rightSum[n-1] + leftSumMax[n-2]
i를 n-2부터 1까지 역방향으로 반복하며 rightAns := max(rightAns, rightSum[i] + leftSumMax[i-1])로 갱신
curr := v[0], kadane := v[0]으로 초기화한 뒤 i를 1부터 n-1까지 반복:
curr := max(v[i], curr + v[i])
kadane := max(curr, kadane)leftAns, rightAns, kadane 세 값 중 최댓값을 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSubarraySumCircular(vector<int>& v) {
int n = v.size();
vector<int> leftSum(n), leftSumMax(n), rightSum(n), rightSumMax(n);
leftSum[0] = v[0];
leftSumMax[0] = max((int)0, v[0]);
for(int i = 1; i < n; i++){
leftSum[i] = leftSum[i-1] + v[i];
leftSumMax[i] = max(leftSum[i], leftSumMax[i-1]);
}
rightSum[n-1] = v[n-1];
rightSumMax[n-1] = max((int)0, v[n-1]);
for(int i = n-2; i >= 0; i--){
rightSum[i] = rightSum[i+1] + v[i];
rightSumMax[i] = max(rightSumMax[i+1], rightSum[i]);
}
int leftAns = leftSum[0] + rightSumMax[1];
for(int i = 1; i < n-1; i++){
leftAns = max(leftAns, leftSum[i] + rightSumMax[i+1]);
}
int rightAns = rightSum[n-1] + leftSumMax[n-2];
for(int i = n-2; i >= 1; i--){
rightAns = max(rightAns, rightSum[i] + leftSumMax[i-1]);
}
int curr = v[0];
int kadane = v[0];
for(int i = 1; i < n; i++){
curr = max(v[i], curr + v[i]);
kadane = max(curr, kadane);
}
return max(leftAns, max(rightAns, kadane));
}
};
main(){
vector<int> v = {1,-2,3,-2};
Solution ob;
cout << (ob.maxSubarraySumCircular(v));
}
실행 결과
입력:
[1,-2,3,-2]
출력:
3
복잡도 분석
이 알고리즘은 모든 단계에서 배열을 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 또한 왼쪽·오른쪽 누적 합 계산을 위해 네 개의 보조 배열을 사용하므로 공간 복잡도 역시 O(n)입니다. 카데인 알고리즘으로 경계를 넘지 않는 경우를 처리하고, 양방향 누적 합으로 순환 구간을 처리하는 이 조합은 원형 배열 문제를 선형 시간 안에 효율적으로 해결하는 대표적인 기법입니다.