백준 1912: 연속합

//누적되는 부분합보다 새로운 수가 더 클 때 부분합을 다시 시작한다.
#include <iostream>
#include <algorithm>
long long d[100050];
int num[100050];
using namespace std;
int main()
{
    int input;
    cin >> input;
    for (int i = 1; i <= input; ++i)
    {
        cin >> num[i];
    }
    d[1] = num[1];
    for (int i = 1; i <= input; ++i)
    {
        d[i] = d[i - 1] + num[i];
        //새로 부분합을 시작하는 경우
        if (d[i] < num[i])
            d[i] = num[i];
    }
    long long ans = d[1];
    for (int i = 1; i <= input; ++i)
        ans = max(ans, d[i]);
    cout << ans << endl;
    return 0;
}