연속합 / 1912번 백준

문제 

문제 난이도 : 실버 2

문제 분류 : 다이나믹 프로그래밍

 

문제 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

vector<int> List;

int main()
{
    //Input
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        int Tmp;
        cin >> Tmp;
        List.push_back(Tmp);
    }
    vector<int> DP(List.size(), 0);
    //Main Logic Start
    //Find Sum of N Elements
    DP[0] = List[0];
    int MaxVal = List[0];
    for (int i = 1; i < n; ++i)
    {
        DP[i] = max(DP[i - 1] + List[i], List[i]);
        MaxVal = max(MaxVal, DP[i]);
    }
    if (n == 1)
    {
        cout << List[0];
    }
    else
    {
        cout << MaxVal;
    }
}