Kadane's Algorithm(카데인 알고리즘)

Kadane's Algorithm은 연속된 부분 수열의 최대 합을 찾는 알고리즘으로, 동적 계획법(Dynamic Programming)을 기반으로 한다. 이 알고리즘은 O(n)의 시간 복잡도로 효율적으로 해결할 수 있다.

알고리즘 목표

• 입력: 길이 n인 수열 arr (음수와 양수 모두 포함 가능).
• 목표: 이 수열에서 연속된 부분 수열 중에서 그 합이 가장 큰 값을 찾는 것.

알고리즘의 기본 아이디어

• 연속된 수들의 합이 최대가 되는 구간을 찾기 위해, 각 인덱스에서 끝나는 부분 수열의 최대 합을 동적으로 계산.
• 특정 위치에서 연속된 부분 수열의 최대 합을 구하려면 그 위치에서 "현재까지 계산된 최대 연속합"을 유지하면서, 그 값을 계속 갱신해 나가는 방식으로 해결.

구체적인 알고리즘 흐름

1. 초기화:
   • 첫 번째 원소를 currentSum (현재까지의 부분 합)과 maxSum (최대 부분 합)으로 초기화.
     • currentSum: 현재 위치까지의 연속된 부분 수열 중 최대 합.
     • maxSum: 전체에서 가장 큰 연속 부분 합.
2. 현재 값과 이전 부분 합을 비교:
   • 각 인덱스에서 다음 두 값 중 큰 것을 currentSum으로 설정:
     1. 현재 값: 새로운 부분 수열을 시작할지.
     2. 이전 값에 현재 값을 더한 것: 기존 부분 수열을 이어서 계속할지.
   • 즉, 현재 값 자체로 새로운 부분 수열을 시작할지 아니면 이전 부분 수열에 이어서 계속할지를 선택.
3. 최대값 갱신:
   • 매 단계마다 maxSum을 갱신합니다. currentSum이 현재까지의 maxSum보다 크면 maxSum을 업데이트.
4. 최종 결과:
   • 배열을 끝까지 탐색한 후 maxSum을 출력한다. 이것이 최대 연속 부분 수열의 합이 된다.

단계별 예시 (배열: {-2, 1, -3, 4, -1, 2, 1, -5, 4})

인덱스	원소 값	currentSum	maxSum
0	-2	-2	-2
1	1	max(1, -2 + 1) = 1	max(-2, 1) = 1
2	-3	max(-3, 1 - 3) = -2	max(1, -2) = 1
3	4	max(4, -2 + 4) = 4	max(1, 4) = 4
4	-1	max(-1, 4 - 1) = 3	max(4, 3) = 4
5	2	max(2, 3 + 2) = 5	max(4, 5) = 5
6	1	max(1, 5 + 1) = 6	max(5, 6) = 6
7	-5	max(-5, 6 - 5) = 1	max(6, 1) = 6
8	4	max(4, 1 + 4) = 5	max(6, 5) = 6

maxSum이 6으로, 이 배열에서 가장 큰 연속 부분 합은 6이다. ([4, -1, 2, 1] 구간의 합).

코드 구현 (자바)

public class Kadane {
    public static int maxSubArraySum(int[] arr) {
        int currentSum = arr[0];  // 현재까지의 연속 부분합
        int maxSum = arr[0];      // 전체 최대 연속 부분합

        for (int i = 1; i < arr.length; i++) {
            // 현재 값과 현재 값 + 이전까지의 연속 부분합 중 더 큰 값 선택
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            // 현재까지의 최대값을 업데이트
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;  // 최대 연속 부분합 반환
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum contiguous sum is " + maxSubArraySum(arr));
    }
}

요약

Kadane's Algorithm은 현재 값으로부터 새로운 부분 수열을 시작할지 또는 기존 부분 수열을 유지할지를 동적으로 선택한다. 이를 통해 전체 배열을 한 번만 순회하면서 최대 연속 부분합을 효율적으로 계산할 수 있다.

 

여담

https://www.acmicpc.net/problem/13398 이 문제를 풀면서 알게 된 알고리즘이다.
공부하면서 정리한거라 틀린 내용이 있을 수 있습니다.