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

카데인 알고리즘(Kadane's algorithm)은 배열의 최대 부분 합을 O(n)의 시간복잡도로 구하는 알고리즘이다.

i번째 인덱스를 오른쪽 끝으로 하는 부분배열들의 최대 부분 합을 M[i]라고 하면, M[i+1]은 M[i]+arr[i+1]이거나 arr[i+1]중 더 큰 값이다.

 

M[0]은 arr[0]인 1이다.

M[1]은 arr[1] = -6과 M[0] + arr[1] = -5 중 더 큰 -5이다.

M[2]는 arr[2] = 4와 M[1] + arr[2] = -1 중 더 큰 4이다.

 

왜 M[i+1]이 max(M[i] + array[i+1], array[i+1]) 인지 이해하면 쉽다.

i를 오른쪽 끝으로 하는 부분배열 중 최대 부분 합이 음수이면 굳이 더하지 않고 그냥 i+1번째 인덱스부터 새로 더하는게 당연히 이득이기 때문이다.

근데 카데인이라고 읽는 게 맞나? 카다네라고 읽고 싶은 기분이 듦.

---

구현하기 |

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n, array[100000], m[100000];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> array[i];
    }
    m[0] = array[0];
    int res = m[0];
    for (int i = 1; i < n; i++)
    {
        res = max(res, m[i] = max(m[i - 1] + array[i], array[i]));
    }
    cout << res;
}

---

관련 문제 |

[BOJ] 연속합 (acmicpc.net/problem/1912)

[BOJ] 보석 줍기 (https://www.acmicpc.net/problem/2208)