가장 큰 연속적인 서브 배열의 합을 구하는 문제입니다.
A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
예를 들어 위의 배열에서 가장 큰 합을 가지는 연속적인 서브 배열은 [4, -1, 2, 1](합 6) 입니다. 이제 아래에서 이 배열을 가지고 브루드 포스와 카데인 알고리즘으로 접근해서 문제를 풀이해보겠습니다.
브루드 포스 접근
브루드 포스는 모든 서브 배열의 합을 계산한 후 거기서 최댓값을 찾는 것입니다.
그림과 같이 인덱스 0 부터 시작해서 A[0]로 시작하는 모든 서브 배열의 합을 계산합니다. 그 후 인덱스를 증가해 A[1],A[2],....,A[n-1] 에서 시작하는 모든 서브 배열의 합을 차례대로 구해나갑니다.
과정을 설명하면
1. 부분 배열 생성 및 합 계산
배열 A의 인덱스 0번부터 시작해서, A[0]으로 시작하는 모든 부분 배열의 합을 구합니다. 그다음 A[1]에서 시작하는 부분 배열, A[2]에서 시작하는 부분 배열을 각각 차례로 생성해나가며 부분 배열의 합을 계산합니다.
2. 최대 합 갱신
각 부분 배열의 합을 구할 때마다 최대 합과 비교하여 더 큰 값이 나오면 최대 합을 갱신합니다.
3. 시간 복잡도 분석
이 방식은 모든 가능한 시작점과 끝점을 살펴보므로, 시간 복잡도가 O(n^2) 이상으로 커집니다. 따라서 큰 배열에서는 비효율적이며, 시간 초과가 발생할 가능성이 큽니다.
public int maxSubArrayBruteForce(int[] A) {
int maxSum = Integer.MIN_VALUE;
int n = A.length;
for (int start = 0; start < n; start++) {
int currentSum = 0;
for (int end = start; end < n; end++) {
currentSum += A[end];
maxSum = Math.max(maxSum, currentSum);
}
}
return maxSum;
} 1. start = 0
• end = 0 부분 배열 [-2] → 합: -2
• end = 1 부분 배열 [-2, 1] → 합: -1
• end = 2 부분 배열 [-2, 1, -3] → 합: -4
• end = 3 부분 배열 [-2, 1, -3, 4] → 합: 0
• end = 4 부분 배열 [-2, 1, -3, 4, -1] → 합: -1
• end = 5 부분 배열 [-2, 1, -3, 4, -1, 2] → 합: 1
• end = 6 부분 배열 [-2, 1, -3, 4, -1, 2, 1] → 합: 2
• end = 7 부분 배열 [-2, 1, -3, 4, -1, 2, 1, -5] → 합: -3
• end = 8 부분 배열 [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 합: 1
현재까지 최대 합: 2
2. start = 1
• end = 1 부분 배열 [1] → 합: 1
• end = 2 부분 배열 [1, -3] → 합: -2
• end = 3 부분 배열 [1, -3, 4] → 합: 2
• end = 4 부분 배열 [1, -3, 4, -1] → 합: 1
• end = 5 부분 배열 [1, -3, 4, -1, 2] → 합: 3
• end = 6 부분 배열 [1, -3, 4, -1, 2, 1] → 합: 4 (최대값 갱신)
• end = 7 부분 배열 [1, -3, 4, -1, 2, 1, -5] → 합: -1
• end = 8 부분 배열 [1, -3, 4, -1, 2, 1, -5, 4] → 합: 3
카데인 알고리즘이란 ?
브루드 포스 방식으로 문제를 해결 할 수 있지만, 시간 초과로 틀리게 되면 카데인 알고리즘을 이용하여 O(N)으로 문제를 해결 할 수 있다!
1. 현재 위치까지의 누적합 유지
배열을 왼쪽에서 오른쪽으로 순회하면서, 현재 위치까지의 누적합(currentSum)을 계산합니다.
2. 최대 합 갱신
매 단계에서 currentSum이 최대 합(maxSum)보다 크다면 maxSum을 갱신합니다.
3. 음수인 누적합 초기화
currentSum이 음수가 되면, 이후에 나올 값을 더해도 합이 작아지므로 currentSum을 0으로 초기화하고 다음 인덱스부터 새로운 부분 배열을 시작합니다.
4. 시간 복잡도
배열을 한 번 순회하면서 해결하므로 시간 복잡도는 O(n)으로 효율적입니다.
public int maxSubArrayKadane(int[] A) {
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
for (int num : A) {
currentSum += num;
maxSum = Math.max(maxSum, currentSum);
if (currentSum < 0) {
currentSum = 0;
}
}
return maxSum;
}
1. A[0] = -2
currentSum = 0 + (-2) = -2
maxSum = max(Integer.MIN_VALUE, -2) = -2
currentSum < 0이므로 currentSum = 0
2. A[1] = 1
currentSum = 0 + 1 = 1
maxSum = max(-2, 1) = 1
currentSum은 양수이므로 그대로 유지
3. A[2] = -3
currentSum = 1 + (-3) = -2
maxSum = max(1, -2) = 1
currentSum < 0이므로 currentSum = 0
4. A[3] = 4
currentSum = 0 + 4 = 4
maxSum = max(1, 4) = 4
currentSum은 양수이므로 그대로 유지
5. A[4] = -1
currentSum = 4 + (-1) = 3
maxSum = max(4, 3) = 4
currentSum은 양수이므로 그대로 유지
.
.
.
9. A[8] = 4
currentSum = 1 + 4 = 5
maxSum = max(6, 5) = 6
최종 결과
• maxSum = 6
결론
두 가지 방법으로 최대 부분 배열의 합을 구할 수 있지만, 카데인 알고리즘은 O(n)의 시간 복잡도를 가지므로 큰 배열에서도 빠르고 효율적입니다. 브루트 포스는 작은 배열에서는 작동하지만, n이 커질수록 비효율적이라 시간 초과가 발생할 수 있습니다.
