최대 합 연속 부분 배열 문제 – 동적 계획법(카데인 알고리즘)으로 해결하기

정수로 이루어진 배열이 주어졌을 때, 연속된 요소들로 구성된 부분 배열(subarray) 중 그 합이 가장 큰 값을 찾아 출력하는 것이 이 문제의 목표입니다.

이 문제는 동적 계획법(Dynamic Programming), 특히 카데인 알고리즘(Kadane's Algorithm)을 활용하면 선형 시간 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 현재 위치까지의 최대 합을 계속 갱신하며 저장하는 것입니다.

문제 예시

입력: 정수 배열 {-2, -3, 4, -1, -2, 1, 5, -3}
출력: 부분 배열의 최대 합은 7

위 예시에서 최대 합은 {4, -1, -2, 1, 5} 구간의 합인 7입니다.

알고리즘

maxSum(array, n)

입력 − 원본 배열과 배열의 크기 n
출력 − 연속 부분 배열의 최대 합

Begin
    tempMax := array[0]
    currentMax := tempMax
    for i := 1 to n-1, do
        currentMax := max(array[i], currentMax + array[i])
        tempMax := max(currentMax, tempMax)
    done
    return tempMax
End

알고리즘 동작 원리

currentMax는 현재 인덱스 i를 끝으로 하는 부분 배열의 최대 합을 의미합니다. 매 단계마다 다음 두 가지 중 더 큰 값을 선택합니다.

• 현재 요소 arr[i]부터 새로운 부분 배열을 시작하는 경우
• 기존 부분 배열에 arr[i]를 이어 붙이는 경우 (currentMax + arr[i])

tempMax는 지금까지 등장한 currentMax 값들 중 가장 큰 값, 즉 최종 정답을 저장하는 변수입니다.

C++ 예제 코드

#include<iostream>
using namespace std;

int maxSum(int arr[], int n) {
    int tempMax = arr[0];
    int currentMax = tempMax;

    for (int i = 1; i < n; i++) { // 최댓값 탐색
        currentMax = max(arr[i], currentMax + arr[i]);
        tempMax = max(tempMax, currentMax);
    }
    return tempMax;
}

int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = 8;
    cout << "부분 배열의 최대 합은: " << maxSum(arr, n);
}

실행 결과

부분 배열의 최대 합은: 7

시간 복잡도

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 완전 탐색(Brute Force) 방식의 O(n²)보다 훨씬 효율적입니다.