9. 최대 슬라이스 문제 (Maximum Slice Problem) Codility Lesson 한국어 정리본 (JavaScript ver.)

최대 슬라이스 문제란?

주어진 정수 배열 A = [a₀, a₁, ..., aₙ₋₁] 에서 연속된 부분 배열(슬라이스, Slice) 중 합이 최대가 되는 구간을 찾는 문제 이다. 즉, 두 인덱스 p, q (p ≤ q)를 선택하여 A[p] + A[p+1] + ... + A[q] 값이 최대가 되는 경우 를 찾는다.

예를 들어, 다음과 같은 배열이 있을 때:

A = [5, -7, 3, 5, -2, 4, -1];

위 배열에서 최대 합을 갖는 부분 배열은 [3, 5, -2, 4]이며, 합은 10이다.

---

1. O(n³) 시간 복잡도의 비효율적인 방법

모든 가능한 슬라이스를 탐색하여 최댓값을 찾는 방법이다.

JavaScript 코드:

function slowMaxSlice(A) {
    let n = A.length;
    let result = 0;
    
    for (let p = 0; p < n; p++) {
        for (let q = p; q < n; q++) {
            let sum = 0;
            for (let i = p; i <= q; i++) {
                sum += A[i];
            }
            result = Math.max(result, sum);
        }
    }
    return result;
}

시간 복잡도: O(n³) (모든 가능한 슬라이스를 반복 탐색)

---

2. O(n²) 시간 복잡도의 개선된 방법

누적 합(Prefix Sums)을 이용하면 O(n²) 로 개선할 수 있다.

JavaScript 코드:

function quadraticMaxSlice(A) {
    let n = A.length;
    let result = 0;
    
    for (let p = 0; p < n; p++) {
        let sum = 0;
        for (let q = p; q < n; q++) {
            sum += A[q];
            result = Math.max(result, sum);
        }
    }
    return result;
}

시간 복잡도: O(n²) (부분합을 저장하여 중복 계산 제거)

---

3. O(n) 시간 복잡도의 최적화된 방법 (카데인 알고리즘)

아이디어:

• maxEnding 변수에 현재까지의 최대 종료 부분합 을 저장.
• 다음 원소를 추가했을 때, maxEnding 이 양수이면 그대로 더하고, 음수이면 0으로 초기화.
• 전체 배열에서 가장 큰 maxEnding 값을 반환.

JavaScript 코드:

function goldenMaxSlice(A) {
    let maxEnding = 0;
    let maxSlice = 0;
    
    for (let a of A) {
        maxEnding = Math.max(0, maxEnding + a);
        maxSlice = Math.max(maxSlice, maxEnding);
    }
    
    return maxSlice;
}

시간 복잡도: O(n) (한 번의 루프만 수행)

 

 

하지만 위의 코드는 모든 배열의 값이 음수일 경우, 잘못된 결과를 반환할 수 있으므로, 올바른 코드는 

function goldenMaxSlice(A) {
    let maxEnding = A[0];
    let maxSlice = A[0];
    
    for (let i = 1; i < A.length; i++) {
        // Either start a new slice at A[i] or continue the previous one
        maxEnding = Math.max(A[i], maxEnding + A[i]);
        maxSlice = Math.max(maxSlice, maxEnding);
    }
    
    return maxSlice;
}