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

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

배열 내의 연속된 부분 배열의 합 중에서 합이 최대인 부분 배열을 찾는 알고리즘이다.

배열을 한 번 순회하면서 현재 위치에서 끝나는 가장 큰 부분 배열의 합을 계산하고 이를 통해 전체 배열에서의 최대 부분 배열 합을 구하는 방식이다.

 

이 알고리즘은 시간 복잡도가 O(n), 공간 복잡도가 O(1)로 매우 효율적이다.

 

또한 1차원 배열뿐만 아니라 2차원 배열에서도 적용할 수 있다.

2차원 배열에서 최대 합을 갖는 부분 행렬을 찾는 문제는 복잡하지만 알고리즘을 행별로 적용하여 문제를 1차원 문제로 축소함으로써 해결할 수 있다.

 

핵심 아이디어

카데인 알고리즘은 다음과 같은 두 가지 값을 사용한다.

1. 현재까지의 최대 부분 배열 합 (current_max) : 특정 위치까지의 최대 부분 배열 합
2. 전체 최대 부분 배열 합 (global_max) : 현재까지의 모든 위치에서 가장 큰 최대 부분 배열 합

 

알고리즘 단계

1. 배열의 첫 번째 원소로 current_max와 global_max를 초기화
2. 배열의 두 번째 원소부터 끝까지 순회하며 다음을 반복
   • 현재 원소를 포함하는 것이 좋을지 아니면 새로 시작하는 것이 더 나은지를 판단하여 current_max를 업데이트
     즉 current_max = max(현재 원소, current_max + 현재 원소)
   • global_max는 current_max와 비교하여 더 큰 값으로 업데이트
3. 모든 요소에 대해 반복이 끝나면 global_max = 최대 부분 배열의 합

 

코드 예제

def kadane(arr):
    # 배열의 첫 번째 원소로 초기화
    current_max = global_max = arr[0]

    # 배열의 두 번째 원소부터 끝까지 순회
    for num in arr[1:]:
        # 현재 원소를 포함할지 새로 시작할지 결정
        current_max = max(num, current_max + num)
        # 전체 최대값 갱신
        global_max = max(global_max, current_max)

    return global_max

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(kadane(arr))  # 6

 

동작 과정 예시

배열: [3, -2, 5, -1]

인덱스	요소	current_sum 계산	global_sum 갱신
0	3	current_sum = 3	global_sum = 3
1	-2	current_sum = max(-2, 3 + (-2)) = 1	global_sum = 3
2	5	current_sum = max(5, 1 + 5) = 6	global_sum = 6
3	-1	current_sum = max(-1, 6 + (-1)) = 5	global_sum = 6