C++에서 분할 정복(Divide and Conquer) 알고리즘으로 최대 부분배열 합 구하기

양수와 음수가 섞여 있는 하나의 데이터 배열이 있다고 가정해 보겠습니다. 이때 우리는 연속된 부분배열(contiguous subarray)의 합 중 가장 큰 값을 찾아야 합니다.

예를 들어 배열이 {-2, -5, 6, -2, -3, 1, 5, -6}이라면, 최대 부분배열의 합은 7이며, 이는 {6, -2, -3, 1, 5} 구간의 합에 해당합니다.

분할 정복 접근 방식

이 문제는 분할 정복(Divide and Conquer) 기법으로 효율적으로 해결할 수 있습니다. 전체 시간 복잡도는 O(n log n)으로, 단순한 브루트 포스 방식(O(n²))보다 훨씬 빠릅니다.

알고리즘 단계:

배열을 두 부분으로 나눕니다(Divide)
다음 세 가지 값 중 최대값을 구합니다(Conquer)
- 왼쪽 부분배열의 최대 부분배열 합
- 오른쪽 부분배열의 최대 부분배열 합
- 중간 지점(midpoint)을 가로지르는 부분배열의 최대 합

중간 지점을 가로지르는 경우를 별도로 계산하는 이유는, 최대 부분배열이 정확히 배열의 중간을 넘나들 수 있기 때문입니다. 이 경우 왼쪽 절반의 끝에서부터 거꾸로 확장하며 최대합을 구하고, 오른쪽 절반은 시작점부터 순방향으로 확장하며 최대합을 구한 뒤 두 값을 더하면 됩니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int max(int a, int b, int c) {
    return max(max(a, b), c);
}

// 중간 지점을 가로지르는 부분배열의 최대 합 계산
int getMaxCrossingSum(int arr[], int l, int m, int h) {
    int sum = 0;
    int left = INT_MIN;

    // 왼쪽 절반: mid부터 l까지 역방향 탐색
    for (int i = m; i >= l; i--) {
        sum = sum + arr[i];
        if (sum > left)
            left = sum;
    }

    sum = 0;
    int right = INT_MIN;

    // 오른쪽 절반: mid+1부터 h까지 순방향 탐색
    for (int i = m + 1; i <= h; i++) {
        sum = sum + arr[i];
        if (sum > right)
            right = sum;
    }

    return left + right;
}

// 분할 정복으로 최대 부분배열 합 계산
int maxSubArraySum(int arr[], int low, int high) {
    if (low == high)          // 원소가 하나뿐인 경우
        return arr[low];

    int mid = (low + high) / 2;

    return max(
        maxSubArraySum(arr, low, mid),              // 왼쪽 최대합
        maxSubArraySum(arr, mid + 1, high),         // 오른쪽 최대합
        getMaxCrossingSum(arr, low, mid, high)      // 중간 경계 포함 최대합
    );
}

int main() {
    int arr[] = {-2, -5, 6, -2, -3, 1, 5, -6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_sum = maxSubArraySum(arr, 0, n - 1);
    printf("Maximum contiguous sum is %d", max_sum);
}

실행 결과

Maximum contiguous sum is 7

동작 원리 정리

위 코드의 핵심 로직을 요약하면 다음과 같습니다.

재귀 종료 조건: low와 high가 같으면(부분배열에 원소가 하나만 남으면) 해당 원소를 그대로 반환합니다.
getMaxCrossingSum(): 중간 지점을 반드시 포함하는 최대 합을 구합니다. 왼쪽에서는 mid부터 시작해 l 방향으로, 오른쪽에서는 mid+1부터 시작해 h 방향으로 누적합을 계산하며 각각의 최대값을 유지합니다.
maxSubArraySum(): 왼쪽 결과, 오른쪽 결과, 중간 경계 결과 세 값 중 최대값을 반환하며 재귀적으로 전체 문제를 해결합니다.

참고로 카데인 알고리즘(Kadane's Algorithm)을 사용하면 O(n)의 시간 복잡도로 동일한 문제를 해결할 수 있지만, 분할 정복 방식은 문제를 나누어 해결하는 패러다임을 학습하기에 매우 좋은 예제입니다.