C++로 요소 하나를 제거한 후 최대 부분 배열 합 구하기

문제 설명

정수 N개로 이루어진 배열 arr[]가 주어졌을 때, 먼저 최대 부분 배열(sub-array)의 합을 구한 뒤, 그 부분 배열에서 최대 한 개의 요소를 제거하여 얻을 수 있는 합을 최대화하는 것이 이 문제의 목표입니다.

예를 들어 입력 배열이 {1, 2, 3, -2, 3}이라면 최대 부분 배열은 배열 전체이며 합은 7입니다. 여기서 음수인 -2를 제거하면 남는 배열은 다음과 같습니다.

{1, 2, 3, 3} → 합계 9 (가능한 최댓값)

알고리즘

1. 카데인(Kadane) 알고리즘을 사용하여 최대 부분 배열 합을 구합니다.
2. 구한 최대 합을 기준으로, 현재 구간의 합·길이·최솟값을 함께 추적하면서 카데인 알고리즘을 변형하여 다시 실행합니다.
3. 최대 합에 도달하는 구간에서 가장 작은 요소를 찾아 빼면, 요소 하나를 제거한 효과를 얻을 수 있습니다.
4. 부분 배열이 단일 요소로만 구성된 경우(예: 모든 원소가 음수일 때)에는 제거로 인한 추가 이득이 없으므로 0을 빼서 원래 합을 그대로 반환합니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
int getMaxSubarraySum(int *arr, int n){
    int max = INT_MIN;
    int currentMax = 0;
    for (int i = 0; i < n; ++i) {
        currentMax = currentMax + arr[i];
        if (max < currentMax) {
            max = currentMax;
        }
        if (currentMax < 0) {
            currentMax = 0;
        }
    }
    return max;
}
int getMaxSum(int *arr, int n){
    int cnt = 0;
    int minVal = INT_MAX;
    int minSubarr = INT_MAX;
    int sum = getMaxSubarraySum(arr, n);
    int max = INT_MIN;
    int currentMax = 0;
    for (int i = 0; i < n; ++i) {
        currentMax = currentMax + arr[i];
        ++cnt;
        minSubarr = min(arr[i], minSubarr);
        if (sum == currentMax) {
            if (cnt == 1) {
                minVal = min(minVal, 0);
            } else {
                minVal = min(minVal, minSubarr);
            }
        }
        if (currentMax < 0) {
            currentMax = 0;
            cnt = 0;
            minSubarr = INT_MAX;
        }
    }
    return sum - minVal;
}
int main(){
    int arr[] = {1, 2, 3, -2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
    return 0;
}

코드 동작 방식

• getMaxSubarraySum(): 표준 카데인 알고리즘으로 최대 부분 배열 합을 계산합니다.
• getMaxSum(): 두 번째 순회에서 현재 구간의 합(currentMax), 구간에 포함된 요소 수(cnt), 구간 내 최솟값(minSubarr)을 추적합니다.
• currentMax가 앞서 구한 최대 합(sum)과 일치하는 순간, 해당 구간에서 제거 가능한 최솟값을 minVal에 갱신합니다.
• 최종적으로 sum − minVal을 반환하면 요소 하나를 제거한 후의 최대 합이 됩니다.

배열을 두 번만 순회하면 되므로 시간 복잡도는 O(N), 공간 복잡도는 O(1)로 매우 효율적입니다.

출력

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Maximum sum = 9