[백준 1912번] 연속합 (C++)

https://www.acmicpc.net/problem/1912

1912번: 연속합

---

연속합 문제는 n이 최대 100,000이기 때문에 모든 구간합(Prefix Sum)을 구하는 경우 (100,000 * 100,001) / 2의 경우의 수에 대해 구간합을 구해야하기 때문에, 구간합의 시간 복잡도가 O(1)이어도 시간 초과가 발생할 수 있습니다. 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 

 

알고리즘은 아래와 같습니다.

1. 기존 수열의 합 + 현재 숫자가 현재 숫자보다 큰 경우 즉, 현재 숫자를 연속된 수열에 포함시키는 것이 새로운 수열을 만들어내는 것보다 합이 큰 경우, 현재 숫자를 기존 수열에 포함시킵니다.
2. 기존 수열의 합 + 현재 숫자가 현재 숫자보다 작은 경우 즉, 현재 숫자를 수열에 포함시키느니 현재 숫자 하나로 구성된 새로운 수열을 만들어내는 것이 합이 더 큰 경우, 새로운 수열을 만들어냅니다.
3. 그동안 생성된 수열의 합 중 최대합을 출력합니다.

10
10 -4 3 1 5 6 -35 12 21 -1

위의 테스트 케이스에 대한 d 배열은 아래와 같습니다. (단, a은 입력 받은 수열이고, d 연속된 수열의 합을 기록하는 배열입니다.)

	0	1	2	3	4	5	6	7	8	9
a	10	-4	3	1	5	6	-35	12	21	-1
d	10	6	9	10	15	21	-14	12	33	32

 

위의 알고리즘을 구현한 코드는 아래와 같습니다.

#include <bits/stdc++.h>
using namespace std;

int a[100001], d[100001];
int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];    // 수열 입력 받음
    
    int ans = INT_MIN;
    for(int i = 0; i < n; ++i){
        d[i] = max(a[i], d[i-1] + a[i]);
        ans = max(ans, d[i]);
    }
    cout << ans;
}