카데인 알고리즘(Kadane's Algorithm)을 구현하는 C++ 프로그램

카데인 알고리즘(Kadane's Algorithm)은 정수 배열에서 최대 부분 배열 합(maximum subarray sum)을 효율적으로 찾기 위한 대표적인 동적 계획법(Dynamic Programming) 기반 알고리즘입니다. 연속된 요소들의 합이 가장 커지는 구간을 O(n)의 시간 복잡도로 한 번의 순회만으로 구할 수 있다는 점이 큰 장점입니다.

이 글에서는 카데인 알고리즘의 동작 원리를 살펴보고, 이를 구현한 C++ 프로그램을 예제와 함께 소개하겠습니다.

알고리즘 동작 원리

카데인 알고리즘은 두 개의 변수를 유지하며 배열을 한 번만 순회합니다.

• currentElementMax: 현재 위치에서 끝나는 부분 배열의 최대 합
• highestMax: 지금까지 발견한 전체 최대 합

각 요소를 순회하면서 "현재 요소부터 새로 시작하는 것이 좋은가, 아니면 기존 부분 배열에 이어 붙이는 것이 좋은가"를 판단하여 최댓값을 갱신합니다.

알고리즘 의사 코드

Begin
Function kadanes(int array[], int length):
    Initialize
    highestMax = 0
    currentElementMax = 0
    for i = 0 to length-1
        currentElementMax = max(array[i], currentElementMax + array[i])
        highestMax = max(highestMax, currentElementMax)
    return highestMax
End

C++ 구현 예제

#include<iostream>
using namespace std;
int kadanes(int array[], int length) {
    int highestMax = 0;
    int currentElementMax = 0;
    for(int i = 0; i < length; i++){
        currentElementMax = max(array[i], currentElementMax + array[i]);
        highestMax = max(highestMax, currentElementMax);
    }
    return highestMax;
}
int main() {
    cout << "Enter the array length: ";
    int l;
    cin >> l;
    int arr[l];
    cout << "Enter the elements of array: ";
    for (int i = 0; i < l; i++) {
        cin >> arr[i];
    }
    cout << "The Maximum Sum is: " << kadanes(arr, l) << endl;
    return 0;
}

실행 결과

Enter the array length: 7
Enter the elements of array:
-1
-2
-3
-4
-5
6
7
The Maximum Sum is: 13

결과 분석

위 예제에서 입력 배열은 -1, -2, -3, -4, -5, 6, 7입니다. 음수로만 이루어진 앞부분은 최대 합에 기여하지 못하고, 마지막의 6 + 7 = 13이 최대 부분 배열 합이 됩니다. 프로그램은 이를 정확히 계산하여 13을 출력합니다.

참고 사항

• 위 구현은 모든 요소가 음수일 경우 결과가 0이 되는데, 빈 부분 배열(합 0)을 허용하는 방식입니다. 빈 배열을 허용하지 않으려면 highestMax와 currentElementMax를 첫 번째 요소 값으로 초기화하면 됩니다.
• 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리는 O(1)입니다.