C++에서 접두사 합(Prefix Sum)을 활용한 O(n) 최대 부분 배열 합 구하기

문제 정의

양수와 음수가 섞여 있는 정수 배열이 주어졌을 때, 이 배열에서 구할 수 있는 최대 부분 배열 합(Maximum Subarray Sum)을 찾는 문제입니다.

예시

입력 배열이 {-12, -5, 4, -1, -7, 1, 8, -3}라고 가정해 보겠습니다. 이때 최대 부분 배열은 {1, 8}이며, 그 합인 9가 결과로 출력됩니다.

알고리즘

접두사 합(Prefix Sum)을 활용하면 반복문 한 번만으로 문제를 해결할 수 있어 시간 복잡도가 O(n)입니다. 핵심 아이디어는 "특정 지점에서 끝나는 최대 부분 배열 합 = 현재 접두사 합 − 지금까지 등장한 최소 접두사 합"이라는 것입니다.

• 입력 배열의 접두사 합(prefix sum)을 계산합니다.

• minPrefixSum = 0, res = int 자료형의 최솟값으로 초기화합니다.

• i = 0부터 n-1까지 반복문을 수행합니다. (n은 입력 배열의 크기)

  • cand = prefixSum[i] - minPrefixSum을 계산합니다.

  • cand가 res(현재까지의 최대 부분 배열 합)보다 크면 res를 cand로 갱신합니다.

  • prefixSum[i]가 minPrefixSum(현재까지의 최소 접두사 합)보다 작으면 minPrefixSum을 prefixSum[i]로 갱신합니다.

• res를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int maximumSumSubarray(int *arr, int n){
    int minPrefixSum = 0;
    int res = numeric_limits<int>::min();
    int prefixSum[n];
    prefixSum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i - 1] + arr[i];
    }
    for (int i = 0; i < n; i++) {
        res = max(res, prefixSum[i] - minPrefixSum);
        minPrefixSum = min(minPrefixSum, prefixSum[i]);
    }
    return res;
}
int main(){
    int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Result = " << maximumSumSubarray(arr, n) <<endl;
    return 0;
}

실행 결과

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

Result = 9

동작 원리 요약

배열을 순회하는 동안 각 위치 i에서 "prefixSum[i]에서 과거의 최소 접두사 합을 뺀 값"은 곧 i에서 끝나는 부분 배열 중 가장 큰 합이 됩니다. 모든 위치에 대해 이 값을 확인하면 전체 최대 부분 배열 합을 구할 수 있으며, 접두사 합 계산과 최댓값 탐색이 각각 한 번의 순회로 처리되므로 전체 과정은 선형 시간(O(n)) 안에 완료됩니다.