카데인 알고리즘

카데인 알고리즘이란?

카데인 알고리즘은 연속 부분 배열의 최대 합을 구하는 효율적인 방법으로, 컴퓨터 과학과 알고리즘 문제 해결에서 자주 사용됩니다. 이 알고리즘은 O(n) 시간 복잡도를 가지며, 동적 계획법(Dynamic Programming) 접근법을 사용합니다.

---

카데인 알고리즘의 원리

카데인 알고리즘은 현재까지의 최대 부분 배열의 합을 유지하면서, 각 요소를 순차적으로 탐색합니다. 알고리즘은 두 가지 값을 유지합니다.

현재까지의 최대 합 (max_so_far) : 지금까지 발견한 최대 부분 배열의 합
현재 위치에서 끝나는 최대 합 (max_ending_here) : 현재 위치에서 끝나는 부분 배열 중 최대 합

---

알고리즘 단계

1. max_so_far와 max_ending_here를 배열의 첫 번째 요소로 초기화합니다.
2. 배열의 두 번째 요소부터 순차적으로 탐색합니다.
3. 각 요소마다 max_ending_here를 업데이트합니다:
   -  max_ending_here = max(array[i], max_ending_here + array[i])
4. max_so_far를 현재 max_ending_here와 비교하여 더 큰 값을 저장합니다:
   -  max_so_far = max(max_so_far, max_ending_here)
5. 배열의 끝까지 탐색한 후 max_so_far를 반환합니다.

Java 구현

public class KadaneAlgorithm {
    // 카데인 알고리즘을 구현하는 함수
    public static int kadaneAlgorithm(int[] array) {
        // 배열의 첫 번째 요소로 초기화
        int maxSoFar = array[0];
        int maxEndingHere = array[0];
        
        // 배열의 두 번째 요소부터 탐색
        for (int i = 1; i < array.length; i++) {
            // 현재 요소를 포함하여 최대 합을 구함
            maxEndingHere = Math.max(array[i], maxEndingHere + array[i]);
            // 현재까지의 최대 합을 갱신
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        
        return maxSoFar;
    }

    // 메인 함수
    public static void main(String[] args) {
        int[] array = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("최대 부분 배열 합: " + kadaneAlgorithm(array));
    }
}

---

알고리즘의 시간 복잡도 분석

카데인 알고리즘은 각 요소를 한 번씩만 탐색하므로, 시간 복잡도는 O(n)입니다. 이는 배열의 크기가 커지더라도 비교적 빠르게 실행된다는 것을 의미합니다.

---

추가 예제와 응용

모든 요소가 음수인 경우: 카데인 알고리즘은 음수 배열에서도 동작합니다. 가장 덜 부정적인 값을 반환합니다.
0이 포함된 경우: 0이 포함된 배열에서도 정상적으로 작동하며, 최대 합을 정확히 계산합니다.