정수 배열이 주어졌을 때, 최대 한 개의 원소를 삭제할 수 있다는 조건에서 비어 있지 않은 연속 부분 배열의 최대 합을 구하는 문제입니다. 즉, 부분 배열을 하나 선택한 뒤 원한다면 그중 원소 하나를 제거할 수 있으며, 삭제 후에도 최소 한 개 이상의 원소가 남아 있어야 하고 남은 원소들의 합이 가능한 한 최대가 되어야 합니다.
예를 들어 입력이 [1, -2, 0, 3]이라면 출력은 4입니다. 여기서 -2를 삭제하면 나머지 원소들의 합인 4가 최댓값이 되기 때문입니다.
접근 방법: 동적 계획법(DP)
이 문제는 카데인 알고리즘(Kadane's Algorithm)을 변형한 방식으로 해결할 수 있습니다. 핵심은 각 인덱스까지 고려했을 때 두 가지 상태를 동시에 추적하는 것입니다.
- 삭제 없이 끝나는 최대 합: 현재 위치에서 끝나는 부분 배열 중 원소를 하나도 삭제하지 않은 경우의 최대 합
- 삭제를 사용해 끝나는 최대 합: 현재 위치에서 끝나는 부분 배열 중 정확히 원소 하나를 삭제한 경우의 최대 합
배열을 순회하면서 이 두 값을 갱신하고, 매 단계마다 전체 최댓값을 업데이트하면 선형 시간 O(n)에 답을 구할 수 있습니다.
알고리즘 단계
- 배열 크기를 n으로 설정하고, 초기 답 ans를 a[0]으로 둡니다.
- 삭제를 사용한 경우의 합(suffix_with_deletion)은 0으로, 삭제하지 않은 경우의 합(suffix_without_deletion)은 a[0]으로 초기화합니다.
- i를 1부터 n-1까지 반복하며 다음을 수행합니다.
- suffix_with_deletion = max(suffix_with_deletion + a[i], suffix_without_deletion)
- suffix_without_deletion = max(a[i], suffix_without_deletion + a[i])
- ans = max(ans, suffix_without_deletion, suffix_with_deletion)
- 최종적으로 ans를 반환합니다.
C++ 구현 예시
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maximumSum(vector<int>& a) {
int n = a.size();
int ans = a[0];
int suffix_with_deletion = 0;
int suffix_without_deletion = a[0];
for(int i = 1; i < n; i++){
suffix_with_deletion = max(suffix_with_deletion + a[i], suffix_without_deletion);
suffix_without_deletion = max(a[i], suffix_without_deletion + a[i]);
ans = max({ans, suffix_without_deletion, suffix_with_deletion});
}
return ans;
}
};
main(){
vector<int> v = {1,-2,0,3};
Solution ob;
cout << ob.maximumSum(v);
}입력
[1,-2,0,3]
출력
4
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회합니다.
- 공간 복잡도: O(1) — 추가 변수 몇 개만 사용합니다.