카데인 알고리즘

카데인 알고리즘이란?

전체 배열에서의 최대 부분합을 구하는 문제이다. Brute Force 방식으로 문제를 어렵지 않게 해결할 수 있지만, 카데인 알고리즘을 이용하면 O(N)으로 문제를 해결할 수 있다.

위 문제에서 결과값인 11이 어떻게 나온 것일까?

1. Brute Force

i = 0, j = 0일 때 => 1
i = 0, j = 1일 때 => max(1, -1) = 1
i = 0, j = 2일 때 => max(1, 2) = 2
... 즉 i번째 인덱스가 포함된 배열 중 최대값을 구하고 그 중에서 최대값을 구하면 된다. 하지만 이 방법은 O(N^2)이라는 시간복잡도를 가진다.

2. 카데인 알고리즘

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]가 주어졌을 때 부분배열의 최대합 문제를 구할 때 사용하는 알고리즘이다.

cursum = max(cursum + nums[i], nums[i])
maxsum = max(cursum, maxsum) 이다.
이것을 코드로 나타내면 다음과 같다.

이 알고리즘을 사용하면 (N) 시간복잡도로 구할 수 있다.