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

숫자 배열을 인자로 받는 JavaScript 함수를 작성해야 합니다. 이 배열에는 양수와 음수가 모두 포함될 수 있습니다.

함수의 목적은 배열 내에서 연속된 요소들로 이루어진 부분 배열(subarray) 중, 그 합이 최대가 되는 부분 배열을 찾아 해당 합을 반환하는 것입니다. 부분 배열의 길이에는 제한이 없습니다.

문제 예시

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

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

이 경우 기대하는 출력은 다음과 같습니다.

const output = 6;

그 이유는 [4, -1, 2, 1]이라는 부분 배열의 합이 6으로, 가능한 모든 부분 배열 중 가장 크기 때문입니다.

접근 방법: 카데인 알고리즘(Kadane's Algorithm)

이 문제는 동적 계획법(Dynamic Programming)의 대표적인 예인 카데인 알고리즘을 사용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 배열을 순회하면서 각 위치마다 다음 두 가지 중 더 큰 값을 선택하는 것입니다.

이전까지의 누적 합에 현재 요소를 더하기
현재 요소부터 새로운 부분 배열을 시작하기

여기서 두 변수를 활용합니다.

sum: 현재 위치에서 끝나는 부분 배열의 최대 합
max: 지금까지 발견된 전체 최대 합

코드 구현

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

const maxSubArray = (arr = []) => {
   let sum = arr[0], max = arr[0];
   for (let i = 1; i < arr.length; ++i) {
      sum = Math.max(sum + arr[i], arr[i]);
      max = Math.max(max, sum);
   }
   return max;
};

console.log(maxSubArray(arr));

출력 결과

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

동작 원리 상세 설명

배열을 한 번 순회하면서 각 단계에서 다음 두 값을 비교합니다.

이전까지의 누적 합(sum)에 현재 요소를 더한 값
현재 요소부터 새로운 부분 배열을 시작하는 값

둘 중 더 큰 값을 sum으로 유지하고, 매번 max와 비교하여 전체 최댓값을 갱신합니다. 만약 누적 합이 현재 요소보다 작다면, 이전 부분 배열은 오히려 손해이므로 버리고 새로 시작하는 것이 유리합니다.

이 알고리즘은 배열을 딱 한 번만 순회하므로 시간 복잡도는 O(n), 추가 공간은 상수만 사용하므로 공간 복잡도는 O(1)입니다. 브루트포스 방식(O(n²))으로 모든 부분 배열의 합을 일일이 계산하는 것보다 훨씬 효율적입니다.