문제 이해하기
정수 배열 arr을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.
여기서 배열 arr은 원형(circular) 배열로 간주할 수 있습니다. 즉, 배열의 마지막 요소 다음에 다시 첫 번째 요소가 이어지는 구조입니다. 우리 함수는 이 배열에서 비어 있지 않은(non-empty) 하위 배열(subarray) 중 가장 큰 합을 찾아 반환해야 합니다.
입력 예시
const arr = [2, -2, 3, -1];
출력 예시
const output = 4;
출력 설명
원형 배열의 특성상 마지막 요소 뒤에 첫 요소가 연결되므로, 원하는 하위 배열은 [3, -1, 2]입니다. 이 배열의 합은 3 + (-1) + 2 = 4로, 가능한 모든 하위 배열 중 가장 큰 값입니다.
접근 방식: 카데인 알고리즘(Kadane's Algorithm)의 확장
원형 배열에서 최대 하위 배열 합을 구하려면 두 가지 경우를 고려해야 합니다.
첫 번째 경우: 최대 하위 배열이 배열을 감싸지 않는(wrap하지 않는) 일반적인 경우입니다. 이는 표준 카데인 알고리즘으로 구할 수 있습니다.
두 번째 경우: 최대 하위 배열이 배열의 끝과 시작을 걸쳐 감싸는 경우입니다. 이때의 합은 (배열 전체의 합) − (최소 하위 배열의 합)으로 계산할 수 있습니다. 즉, 합이 최소가 되는 구간을 빼면 나머지 부분이 감싸는 형태의 최대 합이 됩니다.
두 값 중 더 큰 것을 반환하되, 배열의 모든 요소가 음수인 특수한 경우에는 sum - min이 0이 되어 잘못된 결과를 낼 수 있으므로, 이때는 일반 카데인 결과(최대값)를 그대로 반환해야 합니다.
구현 코드
const arr = [2, -2, 3, -1];
const maxSubarraySumCircular = (arr = []) => {
let max = arr[0];
let min = arr[0];
let currentMax = max;
let currentMin = min;
let sum = arr[0];
for (let i = 1; i < arr.length; i++) {
// 일반(비감싸기) 경우의 최대 하위 배열 합 추적
currentMax = arr[i] + Math.max(currentMax, 0);
max = Math.max(max, currentMax);
// 최소 하위 배열 합 추적 (원형 감싸기 경우 계산용)
currentMin = arr[i] + Math.min(currentMin, 0);
min = Math.min(min, currentMin);
// 배열 전체 합 누적
sum += arr[i];
}
// 모든 요소가 음수면 max 반환, 아니면 두 경우 중 큰 값 반환
return max < 0 ? max : Math.max(max, sum - min);
};
console.log(maxSubarraySumCircular(arr));실행 결과
4
동작 원리 정리
위 코드는 배열을 한 번만 순회하면서 다음 세 가지 값을 동시에 추적합니다.
currentMax / max: 현재 위치까지의 연속 합과 지금까지의 최대 하위 배열 합을 갱신합니다. 이전 누적 합이 음수라면 버리고 새로 시작하는 것이 유리합니다(Math.max(currentMax, 0)).
currentMin / min: 반대로 최소 하위 배열 합을 추적합니다. 이는 원형으로 감싸는 경우의 합을 계산하는 데 필요합니다.
sum: 배열 전체의 합을 누적하여, 최종적으로 sum - min으로 감싸기(wrap) 경우의 후보 값을 만듭니다.
이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다. 단일 순회만으로 원형 배열의 모든 가능한 하위 배열 경우를 커버할 수 있다는 점이 핵심입니다.