JavaScript로 최대 합을 가진 연속 부분 배열 찾기 — 카데인 알고리즘 완벽 가이드

양수와 음수가 섞여 있는 정수 배열이 주어졌을 때, 연속된 요소들의 합이 가장 큰 부분 배열을 찾는 JavaScript 함수를 작성해야 합니다.

배열에 음수가 포함되어 있기 때문에 연속 요소들의 합은 양수일 수도 있고 음수일 수도 있습니다. 따라서 단순히 모든 요소를 더하는 것으로는 최댓값을 구할 수 없으며, 합이 가장 커지는 구간만 골라내야 합니다. 최종적으로 함수는 해당 부분 배열 자체를 반환해야 합니다.

문제 예시

입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [-2, -3, 4, -1, -2, 1, 5, -3];

위 배열에서 만들 수 있는 최대 합은 7이며, 이때의 부분 배열은 다음과 같습니다.

const output = [4, -1, -2, 1, 5]; // 4 + (-1) + (-2) + 1 + 5 = 7

해결 코드

다음은 위 문제를 해결하는 JavaScript 코드입니다.

const arr = [-2, -3, 4, -1, -2, 1, 5, -3];

const maximumSubarray = (arr = []) => {
    let max = -Infinity;
    let currentSum = 0;
    let maxStartIndex = 0;
    let maxEndIndex = arr.length - 1;
    let currentStartIndex = 0;

    arr.forEach((currentNumber, currentIndex) => {
        currentSum += currentNumber;

        if (max < currentSum) {
            max = currentSum;
            maxStartIndex = currentStartIndex;
            maxEndIndex = currentIndex;
        }

        if (currentSum < 0) {
            currentSum = 0;
            currentStartIndex = currentIndex + 1;
        }
    });

    return arr.slice(maxStartIndex, maxEndIndex + 1);
};

console.log(maximumSubarray(arr));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[ 4, -1, -2, 1, 5 ]

코드 동작 원리 (카데인 알고리즘)

이 코드는 유명한 카데인 알고리즘(Kadane's Algorithm)을 변형한 방식으로 동작하며, 시간 복잡도는 O(n)으로 매우 효율적입니다. 핵심 로직은 다음과 같습니다.

1. 누적 합 계산

currentSum 변수에 현재 인덱스까지의 누적 합을 계속 더해 나갑니다.

2. 최댓값 갱신

현재 누적 합 currentSum이 지금까지의 최댓값 max보다 크면, 최댓값과 함께 시작 인덱스(maxStartIndex)와 끝 인덱스(maxEndIndex)를 갱신합니다.

3. 음수 구간 버리기

누적 합이 음수가 되면, 이후 요소들에 더할 때 오히려 합을 줄이는 역할만 하게 됩니다. 따라서 currentSum을 0으로 초기화하고, 시작 인덱스를 다음 위치로 옮겨 새로운 부분 배열 탐색을 시작합니다.

4. 결과 슬라이싱

마지막에는 기록해 둔 시작 인덱스와 끝 인덱스를 이용해 arr.slice()로 최대 합을 가지는 실제 부분 배열을 추출하여 반환합니다.

정리

이처럼 카데인 알고리즘을 활용하면 모든 가능한 부분 배열을 일일이 확인하는 브루트포스 방식(O(n²) 또는 O(n³))보다 훨씬 빠르게, 단 한 번의 순회(O(n))만으로 최대 합 부분 배열을 구할 수 있습니다. 면접에서 자주 출제되는 대표적인 동적 계획법(DP) 문제이므로 로직을 정확히 이해해 두는 것이 좋습니다.