최대 부분합을 구할 때 O(log n)의 시간 복잡도로 계산할 수 있는 알고리즘이다.
최대 부분합이란 배열의 연속 부분 집합 중 그 합이 가장 큰 것을 의미한다.
예를 들어, [-2, 1, 3, -1, 2, -6, 3, 1]의 배열에서 최대 부분합은 [1, 3, -1, 2]이다.
Kadene's algorithm은 특정 index를 포함하는 그것까지의 부분합이 두 가지 방법으로 계산될 수 있음을 이용한 것이다.
- index - 1 까지의 부분 합이 양수인 경우: 이전 부분 합 + 현재 값
- index - 1 까지의 부분 합이 음수인 경우: 현재 값.
위 예시의 배열로 각 index에서의 부분합을 구해보자. (prev: 이전 부분 합 배열, cur: 현재 부분 합 배열, sum: 현재 부분 합)
[ -2, 1, 3, -1, 2, -6, 3, 1 ]
- index = 0
- prev: []
- cur: [-2]
- sum: -2
- index = 1 (case 2)
- prev: [-2]
- cur: [1]
- sum: 1
- index = 2 (case 1)
- prev: [1]
- cur: [1, 3]
- sum: 4
- index = 3 (case 1)
- prev: [1, 3]
- cur: [1, 3, -1]
- sum: 3
- index = 4 (case 1)
- prev: [1, 3, -1]
- cur: [1, 3, -1, 2]
- sum: 5
- index = 5 (case 1)
- prev: [1, 3, -1, 2]
- cur: [1, 3, -1, 2, -6]
- sum: -1
- index = 6 (case 2)
- prev: [1, 3, -1, 2, -6]
- cur: [3]
- sum: 3
- index = 7 (case1)
- prev: [3]
- cur: [3, 1]
- sum: 4
이제 최대 부분 합은 sum 중 가장 큰 값을 고르면 된다.
따라서 이 경우 최대 부분합은 index = 4 인 경우의 '5'이다.
이 과정을 코드로 표현하면 다음과 같다.

728x90
'Algorithms' 카테고리의 다른 글
| Levenshtein distance (1) | 2024.02.09 |
|---|---|
| Binary Search Tree (with JavaScript) (0) | 2023.09.09 |
| 누적 합 (feat. 파괴되지 않는 건물) - 2 (0) | 2023.09.05 |
| 누적 합 (feat. 파괴되지 않는 건물) - 1 (0) | 2023.09.05 |
| 위상 정렬 (with JavaScript) (0) | 2023.09.02 |