n개의 정수로 이루어진 배열이 있다고 가정해 보겠습니다. 우리가 찾아야 할 것은 엄격하게 증가하는(strictly increasing) 부분 배열 중에서 합이 가장 큰 값입니다.
예를 들어 배열이 [1, 2, 3, 2, 5, 1, 7]이라면 정답은 8입니다. 이 배열에는 다음과 같이 세 개의 엄격하게 증가하는 부분 배열이 존재합니다.
- {1, 2, 3} → 합 6
- {2, 5} → 합 7
- {1, 7} → 합 8
이 중 최대 합을 가지는 부분 배열은 {1, 7}이며, 그 합은 8입니다.
접근 방법
이 문제를 해결하려면 두 가지 값을 동시에 추적해야 합니다. 바로 최대 합(max_sum)과 현재 합(current_sum)입니다.
배열을 순회하면서 각 원소 arr[i]에 대해 다음 규칙을 적용합니다.
- arr[i]가 이전 원소 arr[i-1]보다 크다면 → 현재 진행 중인 증가 수열에 포함되므로 current_sum에 더합니다.
- 그렇지 않다면 → 새로운 증가 부분 배열의 시작점이 되므로, current_sum을 arr[i]로 초기화합니다. 단, 초기화하기 전에 기존 current_sum이 max_sum보다 큰 경우 최대 합을 갱신합니다.
순회가 끝난 후에는 마지막으로 계산된 current_sum과 max_sum 중 더 큰 값을 반환하면 됩니다. 이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.
예제 코드
#include<iostream>
using namespace std;
int maximum(int a, int b){
return (a>b)?a:b;
}
int maximum_sum_incr_subarr(int array[] , int n) {
int max_sum = 0;
int current_sum = array[0] ;
for (int i=1; i<n ; i++ ) {
if (array[i-1] < array[i])
current_sum = current_sum + array[i];
else {
max_sum = maximum(max_sum, current_sum);
current_sum = array[i];
}
}
return max(max_sum, current_sum);
}
int main() {
int arr[] = {1, 2, 3, 2, 5, 1, 7};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Maximum sum : " << maximum_sum_incr_subarr(arr , n);
}실행 결과
Maximum sum : 8
정리
핵심은 증가 흐름이 끊어지는 지점을 감지하여 그때까지의 누적 합을 최대 합과 비교하는 것입니다. 이렇게 하면 모든 가능한 부분 배열을 일일이 검사하지 않고도 선형 시간 안에 효율적으로 최대 합을 구할 수 있습니다.