Kadane's Algorithm(카다네 알고리즘) SubArray 최대합 구하기

Maximum subarray problem이라는 문제가 있다

N개의 원소를 가진 배열이 있을 때, (i,j)의 연속되는 인덱스를 선택했을 때의 원소 최대 합을 구하는 문제이다

즉 [4, -2, 5, -4, 3, -7, -6, 10, 5]라는 배열이 있을 때 maximum subarray problem의 답은 7~8번째 원소값을 더한 15가 된다.

 

이 때 가능한 해결법은 약 세가지가 있다

 

1️⃣ 모든 인덱스 (i, j)에 대해 sum을 계산한 뒤 maximum값을 구한다

for(int i=0;i<n;i++)
	for (int j = i; j < n; j++) {
		int sum = 0;
		for (int k = i; k <= j; k++)
			sum += arr[k];
		if (sum > maxSum)maxSum = sum;
	}

이 경우는 떠올리기도, 구현도 간편하지만 O(N^3)이라는 극악의 시간복잡도를 자랑한다

 

2️⃣ 1번과 유사하지만, 앞에서 구한 sub sum값을 활용

for (int i = 0; i < n; i++) {
	int sum = 0;
	for (int j = i; j < n; j++) {
		sum += arr[j];
		if (sum > maxSum)maxSum = sum;
	}
}

구간합을 구하기 위해 앞에서 구한 값을 활용해줬다.

(i,j)의 구간 합 = (i,j-1)의 구간 합 + (j)의 원소 값인 점을 이용한다.

하지만 이 경우에도 시간복잡도는 O(N^2)이며, N이 10000을 넘어가면 for문을 1억번 도는 사태가 발생한다

 

3️⃣ Kadane's Algorithm

카다네(카데인) 알고리즘이라고 한다

Dynamic Programming을 사용하는 알고리즘이면서, 시간복잡도를 O(N)에 해결 가능한 효율적인 알고리즘이다

 

DP알고리즘(카다네 알고리즘)을 적용해서 Maximum Subarray Problem을 해결하는 법

1. Subproblem&Recursion

2번에서 적용했던 방법처럼, 이전에 구했던 subarray의 값을 활용한다.

현재 인덱스를 i라고 할 때, (0,i)까지에서 subarray의 최대 부분합은

(0,i-1)까지의 subarray의 부분합을 연장할지 or (i,~)로 시작하는 부분합을 시작할지 결정하면 된다.

 

2. Memoization

i번째 subarray의 최대 부분합을 구할 때, i-1번째 subarray의 최대 부분합을 여러 번 구하는 것을 방지하기 위해 배열에 [(0,i)까지의 배열에서 maximum subarray값]을 저장한다.

따라서, i번째 subproblem의 값은 i-1번째 subproblem의 값에 dependent하다.

그렇기 때문에 0번째 array의 값부터 차례대로 구한다.

 

위와 같은 경우에서는, 중간에 -4가 끼어있어도 3+4+(-4)+6+5 = 14가 정답이다(-4일 때, -4보다 3+4+(-4)가 더 크기 때문에 후자를 택한다).

 

3. Code

maxSum = dp[0] = arr[0];
for (int i = 1; i < n; i++) {
	dp[i] = max(dp[i - 1] + arr[i], arr[i]);
	if (dp[i] > maxSum)
		maxSum=dp[i];
}

 

4. Time Complexity

단순 연산의 시간복잡도는 O(1)이기 때문에, 반복 크기는 입력 size에 비례한다.

따라서 해당 알고리즘의 시간복잡도는 O(N)이다

 

카다네 알고리즘을 적용해서 풀 수 있는 문제

-> www.acmicpc.net/problem/1912