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)이다
카다네 알고리즘을 적용해서 풀 수 있는 문제