C++에서 최대 두 개의 원소 부호 반전 후 구하는 최대 부분 배열 합

이 문제에서는 하나의 배열이 주어지며, 우리의 과제는 최대 두 개의 원소의 부호를 반전(invert)한 후 얻을 수 있는 최대 부분 배열 합(maximum subarray sum)을 찾는 프로그램을 C++로 작성하는 것입니다.

문제 설명

배열 내 임의의 두 숫자의 부호를 뒤집었을 때 가장 큰 합을 만들어내는 부분 배열(subarray)을 찾아야 합니다.

예시를 통해 문제를 이해해 보겠습니다.

입력: array = {-5, 1, 3, 8, -2, 4, 7}
출력: 30
설명: 인덱스 0부터 6까지의 전체 원소를 고려하고, 값이 음수인 -5와 -2의 부호를 반전하면 합이 최대가 되는 배열을 얻을 수 있습니다. (-5 + 1 + 3 + 8 + 2 + 4 + 7 = 30)

해결 접근 방법

이 문제는 동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있습니다. 길이 1부터 n(배열 길이)까지 모든 부분 배열에 대해 최대 합을 검사합니다. 각 부분 배열마다 다음 세 가지 경우를 고려합니다.

경우 1: 부분 배열 내 두 개의 원소를 반전한 후의 최대 합
경우 2: 부분 배열 내 한 개의 원소를 반전한 후의 최대 합
경우 3: 원소를 반전하지 않은 부분 배열의 최대 합

매 반복(iteration)마다 현재까지의 최대 합과 현재 원소를 비교하여 더 큰 값으로 최댓값을 갱신합니다.

계산된 최대 합은 maxSum이라는 이름의 2차원 배열에 저장하며, 최종 결과는 이 2차원 배열의 모든 원소 중 최댓값이 됩니다. 여기서 maxSum[i][0], maxSum[i][1], maxSum[i][2]는 각각 i번째 원소까지 고려했을 때 반전 횟수가 0회, 1회, 2회인 경우의 최대 부분 배열 합을 의미합니다.

예제 코드

위 해결 방법의 구현을 보여주는 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
int findMaxSubarraySum(int a[], int n) {
    int maxSubarraySum = 0;
    int* arr = new int[n + 1];
    for (int i = 1; i <= n; i++)
        arr[i] = a[i - 1];
    int** maxSum = new int*[n + 1];
    for (int i = 0; i <= n; i++)
        maxSum[i] = new int[3];
    for (int i = 1; i <= n; ++i) {
        // 반전 0회: 일반적인 카데인 알고리즘(Kadane's Algorithm)
        maxSum[i][0] = max(arr[i], maxSum[i - 1][0] + arr[i]);
        // 반전 1회: 현재 원소를 반전하거나, 이전 상태에 현재 원소를 더함
        maxSum[i][1] = max(0, maxSum[i - 1][0]) - arr[i];
        if (i >= 2)
            maxSum[i][1] = max(maxSum[i][1], maxSum[i - 1][1] + arr[i]);
        // 반전 2회: 이전 1회 반전 상태에서 현재 원소를 반전하거나, 기존 상태 유지
        if (i >= 2)
            maxSum[i][2] = maxSum[i - 1][1] - arr[i];
        if (i >= 3)
            maxSum[i][2] = max(maxSum[i][2], maxSum[i - 1][2] + arr[i]);
        maxSubarraySum = max(maxSubarraySum, maxSum[i][0]);
        maxSubarraySum = max(maxSubarraySum, maxSum[i][1]);
        maxSubarraySum = max(maxSubarraySum, maxSum[i][2]);
    }
    return maxSubarraySum;
}
int main(){
    int arr[] = {-5, 1, 3, 8, -2, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"최대 두 개의 원소를 반전한 후의 최대 부분 배열 합: "<<findMaxSubarraySum(arr, n);
    return 0;
}

출력 결과

최대 두 개의 원소를 반전한 후의 최대 부분 배열 합: 30

결론

이 접근 방식은 배열을 한 번만 순회하면서 세 가지 상태(반전 0회, 1회, 2회)를 동시에 추적하므로, 시간 복잡도는 O(n), 공간 복잡도는 O(n)으로 효율적입니다. 동적 계획법을 사용하면 가능한 모든 반전 조합을 일일이 확인하는 브루트 포스 방식(O(n²) 이상)보다 훨씬 빠르게 최적해를 구할 수 있습니다.