Kadane 알고리즘: 가장 큰 부분 수열의 합 구하기

tree·2024년 12월 19일

알고리즘

목록 보기

1/1

부분 수열의 합 중 가장 큰 값을 구할 때 흔히 쓰는 방법은 크게 3가지다.
1. Brute-force
2. Divide & Conquer
3. kdane 알고리즘

2번과 3번은 전형적인 DP의 방식은 아니지만 개념적으로는 DP와 비슷하다.

1. Brute-force

가장 단순한 방법으로, 모든 가능한 부분 수열을 계산해서 최대값을 찾는 방식이다. 시간복잡도는 또는 으로 효율적이지 않다. 실제로 작은 입력 크기에서는 괜찮지만, 입력 크기가 커지면 비효율적이다.
약 O(n^2)의 시간 복잡도를 가지고 있다.

2. Divide & Conquer

Divide and Conquer 방식으로 문제를 푼다. 배열을 반으로 나누고, 왼쪽에서의 최대값, 오른쪽에서의 최대값, 그리고 가운데를 걸치는 최대값을 계산한다. 시간복잡도는 O(nlogn)이다. Brute-force보다는 훨씬 효율적이지만 아무래도 재귀호출(스택)을 쓰다보니 공간 메모리를 사용한다.

예시

public class DivideAndConquer {
    public static int maxCrossingSum(int[] nums, int left, int mid, int right) {
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;

        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.max(leftSum, sum);
        }

        sum = 0;
        int rightSum = Integer.MIN_VALUE;

        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.max(rightSum, sum);
        }

        return leftSum + rightSum;
    }

    public static int maxSubArraySum(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }

        int mid = (left + right) / 2;

        int leftMax = maxSubArraySum(nums, left, mid);
        int rightMax = maxSubArraySum(nums, mid + 1, right);
        int crossMax = maxCrossingSum(nums, left, mid, right);

        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int result = maxSubArraySum(nums, 0, nums.length - 1);
        System.out.println(result); // 결과: 6 (부분 수열 [4, -1, 2, 1])
    }
}

Kadane 알고리즘

Kadane 알고리즘은 DP를 활용해서 문제를 푼다. 배열을 한 번만 순회하면서 부분합의 최대값을 찾아낸다. 시간복잡도는 O(n)으로 가장 효율적인 방법이다. 코드도 간단해서 실제로 많이 사용된다.

Kadane 알고리즘 구현

예시

public class Kadane {
    public static int maxSubArraySum(int[] nums) {
        int maxCurrent = nums[0];
        int maxGlobal = nums[0];

        for (int i = 1; i < nums.length; i++) {
            maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
            maxGlobal = Math.max(maxGlobal, maxCurrent);
        }

        return maxGlobal;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArraySum(nums)); // 결과: 6 (부분 수열 [4, -1, 2, 1])
    }
}

Kadane 알고리즘의 핵심 아이디어

현재까지의 부분합(max_current)을 유지하면서 현재 값을 더할지, 아니면 새로 시작할지를 결정한다.
글로벌 최대값(max_global)을 갱신한다.

배열을 한 번만 순회하므로 시간복잡도가 O(n)이다.

사용 사례

Kadane 알고리즘은 아래와 같은 문제에서 활용할 수 있다:

최대 부분 수열의 합 찾기: 코테 문제 https://school.programmers.co.kr/learn/courses/30/lessons/161988
2D 배열에서 최대 부분합 찾기 (Kadane를 확장)
기타 최적화 문제

tree