백준 1912. 연속합

www.acmicpc.net/problem/1912

1912번: 연속합

 

다시 푼 문제.

이전 글: tose33.tistory.com/22

 

 

	1	2	3	4	5	6	7	8	9	10
a	2	1	-4	3	4	-4	6	5	-5	1
d	2	3	-1	3	7	3	9	14	9	10

 

a[i-1] + a[i] 와 a[i] 를 비교해서 큰 값이 d[i]이다.

예를들어 현재 a[3]를 계산중이라고 해보자.

d[2]에는 n = 2 까지의 연속합 중 최대값이 저장되 있고 d[2] = 3이다. 

이제 d[2]에 a[3]을 더한값과 그냥 d[2]중 큰값이 d[3]이 된다.

d[2] + a[3] = -1 이고

a[3] = -4 이므로

d[3] = -1 이다.

 

이제 a[4]를 비교하면

d[3] = -1 이다. 즉 a[3]까지의 연속합 중 최댓값이 -1 이라는 뜻이다.

d[3] + a[4] = 2 이고 a[4] = 3 이므로 d[4] = 3 이다.

 

즉 d[i-1]은 a[i-1]까지의 연속합 중 최댓값이 보장되있으므로 (저장되있으므로)

d[i-1]에 a[i]를 더하면 값이 더 커질지 안커질지를 판단하는 것이다. 

더 커진다면 지금까지의 연속합(d[i-1])에 a[i]를 더하면 되는것이고, 

작아진다면 연속합은 끊기고 d[i]는 a[i]가 되는 것이다. (새로운 연속 시작)

#include <iostream>
using namespace std;

int a[100001];
int d[100001];

int main() {
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++) cin >> a[i];
    d[1] = a[1];

    int ans = d[1];
    for(int i = 2; i <= n; i++) {
        if(d[i-1] + a[i] > a[i]) d[i] = d[i-1] + a[i];
        else d[i] = a[i];

        ans = max(ans, d[i]);
    }

    cout << ans;

}