BOJ 1912 연속합

boj 1912 연속합

간단한 DP 문제이다. a[i]는 수열이 담긴 배열이고, 테이블로 D[i]는 i번째 원소를 마지막으로 하는 연속된 수열 합의 최댓값이라고 정의한다. 합이므로 초기 값은 원소 자기 자신의 값이다. 그러므로 D[i] = a[i]로 초기화한다.
수열이 연속된다는 것을 인지하면 D[i] = max(D[i], D[i-1] + a[i]) 이라는 점화식이 쉽게 만들어진다.
각 수는 -1000에서 1000 사이이 수 이므로 ans는 초기 값으로 -1001을 주었다.
위 내용을 바탕으로 코드를 구현해보자.

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int a[100005];
int D[100005];
int ans = -1001;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    for (int i = 1; i <= n; i++)
    {
        D[i] = a[i];
        D[i] = max(D [i], D[i - 1] + a[i]);
        ans = max(ans, D[i]);
    }

    cout << ans;
}