Kadane 알고리즘

Kadane 알고리즘

“Kadane 알고리즘”은 연속된 부분 수열의 최대 합(Subarray Sum) 을

가장 효율적으로 구할 수 있는 알고리즘이다.

예를 들어 이런 문제가 있다.

“정수 배열이 주어졌을 때, 연속된 부분 구간의 합 중 최대값을 구하시오.”

예시로 이해하기

다음 수열을 보자.

[2, 3, -6, 1, 3, -1, 2, 4]

이 중 연속된 일부 구간을 골라 합이 최대가 되는 경우를 찾고 싶다.

눈으로 보면,

[3, -6, 1, 3, -1, 2, 4] 같은 구간을 여러 개 살펴보게 될 것이다.

하지만 이런 걸 전부 시도하면 너무 오래 걸린다. (최악의 경우 $O(n^2)$)

그래서 Kadane 알고리즘은 “한 번의 순회”만으로 최대 합을 찾아낼 수 있다!

아이디어: “지금까지의 최대 부분합만 기억하자”

이전까지의 구간 합이 양수라면 지금 원소에 더하는 게 이득이다.

반대로 음수라면 굳이 더할 필요 없이 새로 시작하는 게 낫다.

즉, 현재 원소 a[i]에서의 “최대 연속 부분합”은 다음 중 큰 값이다.

현재 원소 a[i]

이를 점화식으로 표현하면 다음과 같다.

알고리즘 동작 예시

이때 dp[i]들 중 가장 큰 값은 9

즉, 연속 부분합 최대값은 9이다.

코드 예시 (Java)

public class Kadane {
    public static long maxSubArraySum(int[] arr) {
        long maxSum = arr[0];
        long current = arr[0];

        for (int i = 1; i < arr.length; i++) {
            // 이전 합 + 현재 값 vs 현재 값 중 큰 쪽 선택
            current = Math.max(arr[i], current + arr[i]);
            maxSum = Math.max(maxSum, current);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] seq = {2, 3, -6, 1, 3, -1, 2, 4};
        System.out.println(maxSubArraySum(seq)); // 9
    }
}

시간 복잡도 분석

• 한 번의 반복문으로 모든 원소를 한 번씩만 확인
• 각 단계에서 max() 연산만 수행