카데인 알고리즘(Kadane's Algorithm)으로 JavaScript 배열의 최대 부분합 구하기

문제 정의

양수와 음수를 모두 포함하는 정수 배열 arr를 유일한 인자로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 배열 내 임의의 연속된 부분 배열(subarray) 중 합이 가장 큰 값을 선형 시간 O(n) 안에 반환해야 합니다.

접근 방식: 카데인 알고리즘

카데인 알고리즘의 핵심 아이디어는 다음과 같습니다. 임의의 인덱스 i에서의 local_maximum(지역 최댓값)은 arr[i] 자신과, arr[i]에 바로 앞 인덱스 i - 1의 지역 최댓값을 더한 값 중 더 큰 쪽입니다.

쉽게 말해, 배열을 순회하면서 각 위치마다 "이전까지의 누적 합을 이어갈 것인가, 아니면 현재 요소부터 새로 시작할 것인가"를 판단하는 방식입니다. 이렇게 하면 배열을 단 한 번만 순회해서도 전체 최대 부분합을 구할 수 있습니다.

예시

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

입력

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

출력

const output = 6;

출력 설명

합이 가장 큰 부분 배열은 다음과 같으며, 그 합은 6입니다.

[4, -1, 2, 1]

구현 예제

다음은 위 알고리즘을 적용한 전체 코드입니다.

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const maxSequence = (arr = []) => {
   let currentSum = 0
   let maxSum = 0

   for (let elem of arr) {
      const nextSum = currentSum + elem
      maxSum = Math.max(maxSum, nextSum)
      currentSum = Math.max(nextSum, 0)
   }

   return maxSum
};
console.log(maxSequence(arr));

출력 결과

코드 동작 원리

currentSum: 현재 위치까지 이어지는 부분 배열의 합을 저장합니다. 값이 음수가 되면 0으로 초기화되어, 사실상 새로운 부분 배열을 시작하게 됩니다.
maxSum: 지금까지 탐색 과정에서 발견한 최대 부분합을 저장합니다.
배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리 사용은 상수 수준으로 공간 복잡도는 O(1)입니다.

참고 사항

위 구현은 maxSum을 0으로 초기화하기 때문에, 배열의 모든 요소가 음수인 경우에는 0(빈 부분 배열을 허용하는 변형 기준)을 반환합니다. 만약 모든 요소가 음수일 때도 실제 최댓값을 반환해야 한다면, maxSum을 -Infinity로 초기화하고 각 단계에서 Math.max(maxSum, currentSum)을 비교하도록 로직을 살짝 수정하면 됩니다.