Kadane 알고리즘

Codility - MaxDoubleSliceSum

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

MaxDoubleSliceSum coding task - Learn to Code - Codility

 

✅ 1. Kadane 알고리즘이란?

👉 연속된 부분 배열의 최대 합을 O(N)에 구하는 알고리즘

 

• 이전까지의 누적합이 음수로 떨어지면,
• 그것은 해가 되므로 잘라내고,
• 0부터 새로 시작하는 방식

---

✅ 2. MaxDoubleSliceSum 문제 설명

문제 정의:

주어진 배열 A에서
(X, Y, Z) 세 인덱스를 고를 때,

• 조건: 0 ≤ X < Y < Z < N
• 합: A[X+1] + A[X+2] + ... + A[Y-1] + A[Y+1] + ... + A[Z-1]

이 합의 최댓값을 구하라.

 

예시:

A = [3, 2, 6, -1, 4, 5, -1, 2]

 

가능한 여러 double slice 중,
(0, 3, 6) → [2,6] + [4,5] → 합은 17

최댓값은 17

---

✅ 3. Kadane 알고리즘을 어떻게 적용했나?

이 문제는 X, Y, Z를 모두 고르는 것처럼 보이지만, 실제로는 Y만 순회하면서 해결할 수 있다.

• A[X]와 A[Z]는 포함하지 않음 -> A[X+1] 부터 A[Z-1] 구간까지만 구함
• 우리는 Y 기준으로 양쪽 내부 구간의 합만 고려하면 됨
• 해가 되는 구간은 Kadane 알고리즘으로 자동 무시됨
• 만약 중간에 해가 되는 구간이 없다면, X와 Z는 자동으로 양쪽 끝 값으로 설정되는 꼴이 됨

따라서 다음과 같은 방식으로 문제를 해결할 수 있다.

1. 왼쪽에서 Y-1까지 최대 부분합을 left[] 배열에 저장
2. 오른쪽에서 Y+1까지 최대 부분합을 right[] 배열에 저장
3. 모든 Y에 대해 left[Y-1] + right[Y+1]의 최댓값을 탐색

---

✅ 4. 최종 코드 (Python)

def solution(A):
    N = len(A)
    left = [0] * N
    right = [0] * N

    # 왼쪽 누적합: 끝나는 지점이 i
    for i in range(1, N - 1):
        left[i] = max(0, left[i - 1] + A[i])

    # 오른쪽 누적합: 시작 지점이 i
    for i in range(N - 2, 0, -1):
        right[i] = max(0, right[i + 1] + A[i])

    max_sum = 0
    for Y in range(1, N - 1):
        max_sum = max(max_sum, left[Y - 1] + right[Y + 1])

    return max_sum