[알고리즘 이론] 카데인 알고리즘(Kadane's Alogrithm)

카데인 알고리즘이란?

참고: sustainable-dev.tistory.com/23

DP 기법 중 하나이다. 앞의 값을 이용해 뒤의 값을 구할 수 있다.

최대 부분 합을 구할 때 사용한다. 1차원 배열에서 부분 배열 중 최대 합을 구하면된다.

핵심코드

for (int i = 0; i < N; i++) {
	sum = Math.max(arr[i], sum + arr[i]);
	max = Math.max(sum, max);
}

 

A[5]까지 부분합은 A[4]의 부분합을 통해서 구할 수 있다.

A[4]의 Sum을 보면, [-1, 3, 0, 1, -1]이라는 값이 있다. 그 다음 A[5]의 Sum을 보면 [1, 5, 2, 3, 1]이 있는데, 이 값들은 이전 A[4]의 배열에서 A[5]의 값인 2를 더해준 값이다.

A[4]의 최대값은 3, A[5]의 최대값은 5로 둘 차이는 2만큼이다.

이 말은, Sum은 모든 값을 가져 갈 필요 없이 내 위치를 포함한 최대값만 가져가면 된다.

 

만약, sum 배열이 음수인데, 더해주는 값이 음수라면?

sum이 -2라고 가정했을때, A[7]과 같이 더해주는 값이 마이너스인 경우 A[7]과 sum+A[7]을 비교해본다.

A[7] = -5

sum + A[7] = -7

sum은 항상 최대값만 가지고가면 이후 부분 배열의 합은 항상 최대를 구할 수 있다.

그저 sum은 A[7]의 값이 들어간 최대만 가지고 있으면 된다. 따라서, sum=A[7]이된다.

 

모든 부분 배열 중 최대 값을 구하기 때문에 각 부분 배열 합 중 max만 비교해주면된다.

 

 

www.acmicpc.net/problem/10211

10211번: Maximum Subarray

관련문제. 카데인 알고리즘으로 풀어보면 된다.