[백준/C,C++] 1912번: 연속합

www.acmicpc.net/problem/1912

1912번: 연속합

DP 문제 중 정말 간단하다 느꼈던 문제입니다. 당장 예제입력인 10 -4 3 1 5 6 -35 12 21 -1 수열을 살펴보겠습니다.

	10	-4	3	1	5	6	-35	12	21	-1
연속합	10	6	9	10	15	21	-14	12	33	32

이전 연속합에 현재 입력값을 더한 값과 입력값 중 큰 값을 갱신해주면 됩니다.

#include<iostream>

using namespace std;

#define MAX 100001

int DP[MAX];

int main(void)
{
    int n; cin >> n;
    int res = -1000;
    
    DP[0] = -1000;
    for (int i = 1; i <= n; i++) {
        int temp; cin >> temp;
        DP[i] = max(temp, DP[i - 1] + temp);
        if (DP[i] > res) {
            res = DP[i];
        }
    }

    cout << res;

    return 0;
}