주어진 배열의 연속하는 일정 구간을 선택해 선택한 구간의 합이 최대가 되도록 하는 문제다. 문제에서 주어진 배열의 크기가 로 상당히 크다. 이상의 알고리즘을 사용하기 힘든 크기다. 완전탐색의 풀이를 고려했을 때, 상수를 제외하면 최대 개의 시작위치와 최대 개의 종료위치를 지정해야하고 각 구간마다 최대 개의 항목을 더해야하므로 시간 복잡도는 이 된다. 따라서 이 문제는 절대 완전탐색으로는 시간안에 해결할 수 없다.
이 문제를 단계별로 구분지어 다시 생각해보자. 직접 값을 더하기 보단, 각 인덱스 별 최적값을 차례대로 찾아나갈 수 있지 않을까? 번째 배열값이 arr[]라고 해보자. 배열에 요소가 하나밖에 없다면 최적값은 항상 arr[] 이므로 이것이 기저 사례다. 이제 배열에 요소가 2개 이상일 때를 생각해보자. 이전 최적값이 양수라면 항상 더하는게 옳다. 현재 요소 arr[]가 어떤 값이든 반드시 더한 값이 더 크다. 현재 요소가 음수이더라도 현재를 포함한 구간의 값이 양수라면 앞으로 추가할 구간에 이어 붙여서 더 큰 구간합을 만들 수 있기 때문에 추가하는게 이득이다. 이전 최적값이 음수라면 당연히 버리고 현재 인덱스부터 새로운 구간을 생성하는 것이 이득이다. 따라서 점화식은 다음과 같다.
어떤 인덱스 로 종료되는 구간의 최적값이 dp[]이라고 할 때, dp[]은 dp[]이 보다 크다면 dp[] + arr[]이고 0보다 작다면 arr[]이다. 이전 최적값이 음수라면 취할 이유가 없으니 현재 배열 인덱스값을 가지고 다시 구간을 만들고 양수면 거기에 이어서 구간을 만드는 것이 최적이다. 단, dp[]는 해당 인덱스를 포함하는 최적값이므로 문제의 전체 최적값을 찾기 위해서는 모든 dp[]를 계산할 때마다 최댓값을 검사해줘야 한다. 각각의 배열 항목들에 대해 한번씩만 계산하면 되므로 시간복잡도는 이 된다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n; vector<int> arr(n + 1), dp(n + 1);
for(int i=1;i<=n;i++) {
cin >> arr[i];
}
int mx = arr[1]; dp[1] = arr[1];
for(int i=2;i<=n;i++) {
if(dp[i - 1] > 0) { // 0보다 큰 경우 ( 이전 구간을 포함하는게 이득 )
dp[i] = dp[i - 1] + arr[i];
}
else { // 0보다 작은 경우 ( 이전 구간을 버리는게 이득 )
dp[i] = arr[i];
}
mx = mx > dp[i] ? mx : dp[i]; // 최댓값 갱신
}
cout << mx;
return 0;
}++ 추가 dp 값을 정하는 것이 조금 어렵게 느껴질 수 있다. 사실 이런 건 문제를 많이 풀면서 감을 쌓는 수 밖에 없다. 해당 문제에서 dp[]가 를 포함하는 최적값인 이유는 구간이 반드시 연속해야하기 때문이다. 현재 인덱스 를 포함하지 않는 최적값은 이미 dp[] 어딘가에 저장되어있기 때문에 계산이 무의미하기 때문이다.