C/C++로 구현하는 최대 합 연속 부분 배열 찾기 프로그램

정수 배열이 주어졌을 때, 배열 내에서 연속된 요소들의 합 중 가장 큰 값을 찾아 출력하는 문제입니다. 이 문제는 흔히 '최대 부분 배열 합(Maximum Subarray Sum)' 문제라고 불리며, 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다.

접근 방식

동적 계획법의 핵심 아이디어는 다음과 같습니다.

• 현재 위치까지의 최대 합(currentMax)을 저장합니다.
• 각 요소를 순회하면서 '현재 요소만 선택하는 경우'와 '이전까지의 합에 현재 요소를 더하는 경우' 중 더 큰 값을 currentMax로 갱신합니다.
• 순회 과정에서 나온 currentMax 값들 중 가장 큰 값을 전체 최대 합(tempMax)으로 유지합니다.

이 방법은 카데인 알고리즘(Kadane's Algorithm)이라고도 하며, 시간 복잡도는 O(n)으로 매우 효율적입니다.

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

알고리즘

maxSum(array, n)

입력 − 원본 배열과 배열의 크기 n

출력 − 연속 부분 배열의 최대 합

Begin
    tempMax := array[0]
    currentMax = tempMax
    for i := 1 to n-1, do
        currentMax = array[i]와 (currentMax + array[i]) 중 최댓값
        tempMax = currentMax와 tempMax 중 최댓값
    done
    return tempMax
End

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

동작 원리 설명

위 예제에서 배열 {-2, -3, 4, -1, -2, 1, 5, -3}의 경우, 인덱스 2부터 6까지의 요소인 {4, -1, -2, 1, 5}가 연속 부분 배열 중 가장 큰 합인 7을 만듭니다.

currentMax는 매 단계마다 '새로운 부분 배열을 시작할지' 아니면 '기존 합에 이어갈지'를 판단합니다. 만약 현재 요소가 이전 누적 합보다 크다면, 새로운 부분 배열을 시작하는 것이 유리하기 때문입니다. 음수가 포함된 배열에서도 올바르게 동작하며, 모든 요소가 음수인 경우에도 가장 작은 절댓값을 가진 단일 요소를 결과로 반환합니다.