이 문제에서는 하나의 배열이 주어지며, 최대 한 개의 요소를 제거했을 때 얻을 수 있는 최대 합 부분 배열(maximum sum subarray)을 찾는 프로그램을 C++로 작성하는 것이 목표입니다.
쉽게 말해, 배열에서 단 하나의 요소를 제거했을 때 남은 요소들의 합이 가장 커지도록 만드는 요소를 찾아야 합니다.
먼저 예시를 통해 문제를 살펴보겠습니다.
입력 − array = {5, 1, 9, 2, -1, 7}
출력 − 24
설명 − 배열에서 -1을 제거하면 가능한 모든 경우 중 가장 큰 합을 얻을 수 있습니다.
문제 해결 접근 방법
이 문제를 해결하는 간단한 방법 중 하나는 배열에서 최솟값을 찾은 뒤, 해당 값을 제외한 나머지 요소들의 합을 구하는 것입니다.
하지만 이 방식은 요소 제거 조건을 제대로 반영하지 못할 수 있습니다. 대신 카데인 알고리즘(Kadane's Algorithm)을 활용하면 더 효율적으로 문제를 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 시작 지점부터 i번째 요소까지의 최대 합(startSum)과, 끝 지점부터 i번째 요소까지의 최대 합(endSum)을 각각 계산합니다.
그런 다음 두 배열을 이용해 특정 i번째 요소를 건너뛰었을 때의 합을 확인하고, 요소를 제거했을 때 얻을 수 있는 최대 합을 구해 출력합니다.
예제 코드
다음은 위 해결 방법을 구현한 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
int maxSubarraySum(int array[], int n){
int startSum[n], endSum[n];
int maxSum = array[0], overAllMax = array[0];
startSum[0] = array[0];
for (int i = 1; i < n; i++){
maxSum = max(array[i], maxSum + array[i]);
overAllMax = max(overAllMax, maxSum);
startSum[i] = maxSum;
}
maxSum = endSum[n-1] = array[n-1];
for (int i = n-2; i >= 0; i--){
maxSum = max(array[i], maxSum + array[i]);
overAllMax = max(overAllMax, maxSum);
endSum[i] = maxSum;
}
int SubArraySum = overAllMax;
for (int i = 1; i < n - 1; i++)
SubArraySum = max(SubArraySum, startSum[i - 1] + endSum[i + 1]);
return SubArraySum;
}
int main()
{
int array[] = {5, 7, 1, -1, 4, 2, 9};
int n = sizeof(array) / sizeof(array[0]);
cout<<"The maximum subarray after removing one element is "<<maxSubarraySum(array, n);
return 0;
}
실행 결과
The maximum subarray after removing one element is 28
동작 원리 정리
이 알고리즘은 다음과 같은 순서로 동작합니다.
- 왼쪽에서 오른쪽으로 진행하며, 각 위치에서 끝나는 최대 부분 배열 합(startSum)을 계산합니다.
- 오른쪽에서 왼쪽으로 진행하며, 각 위치에서 시작하는 최대 부분 배열 합(endSum)을 계산합니다.
- 요소를 제거하지 않은 경우의 최댓값(overAllMax)과, i번째 요소를 제거한 경우의 합(startSum[i-1] + endSum[i+1])을 비교하여 최종 결과를 도출합니다.
이 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(n)으로, 배열을 반복적으로 탐색하는 완전 탐색 방식보다 훨씬 효율적입니다.