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

양수와 음수가 섞여 있는 하나의 배열이 주어졌을 때, 연속된 부분 배열(subarray) 중에서 합이 가장 큰 값을 찾는 문제가 있습니다. 예를 들어 배열이 {-2, -5, 6, -2, -3, 1, 5, -6}이라면, 최대 부분 배열의 합은 7이며, 이는 {6, -2, -3, 1, 5}의 합입니다.

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

알고리즘 동작 원리

분할 정복 방식은 다음과 같은 단계로 진행됩니다.

배열을 두 개의 절반으로 나눕니다.
다음 세 가지 값 중 최댓값을 찾습니다.
- 왼쪽 부분 배열에서의 최대 부분 배열 합
- 오른쪽 부분 배열에서의 최대 부분 배열 합
- 중간 지점(middle)을 가로지르는 부분 배열의 최대 합

핵심 아이디어는 최대 부분 배열이 왼쪽에만 존재하거나, 오른쪽에만 존재하거나, 아니면 중간을 걸쳐 양쪽에 모두 걸쳐 있다는 세 가지 경우 중 반드시 하나에 해당한다는 점입니다. 각 경우를 재귀적으로 처리한 뒤 세 값 중 최댓값을 반환하면 됩니다.

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;
    // 중간부터 왼쪽 끝까지 탐색하며 최대 합 저장
    for (int i = m; i >= l; i--) {
        sum = sum + arr[i];
        if (sum > left)
            left = sum;
    }
    sum = 0;
    int right = INT_MIN;
    // 중간+1부터 오른쪽 끝까지 탐색하며 최대 합 저장
    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);
    return 0;
}

실행 결과

Maximum contiguous sum is 7

코드 설명

getMaxCrossingSum: 중간 인덱스를 기준으로 왼쪽 방향과 오른쪽 방향으로 각각 확장해 나가며 얻을 수 있는 최대 합을 구하고, 두 값을 더해 반환합니다.
maxSubArraySum: 재귀 호출을 통해 배열을 계속 반으로 나누고, 요소가 하나 남으면 그 값을 반환합니다. 이후 왼쪽 결과, 오른쪽 결과, 중간 가로지름 결과 중 최댓값을 선택합니다.
기저 조건(low == high)에 도달하면 재귀가 종료되므로, 전체 알고리즘은 안정적으로 수렴합니다.

참고로 이 문제는 카데인 알고리즘(Kadane's Algorithm)을 사용하면 O(n)의 시간 복잡도로도 해결할 수 있지만, 분할 정복 접근법은 재귀적 사고와 병합 정렬과 유사한 구조를 학습하는 데 매우 유용한 예제입니다.