[백준, DP] 연속합 C++(복습필요)

https://www.acmicpc.net/problem/1912

1912번: 연속합

---

접근법

인덱스	계산	기억값	최대값
1	10 - 4	6	10
2	6 + 3	9	10
3	9 + 1	10	10
4	10 + 5	15	15
5	15 + 6	21	21
6	21 - 35	-14	21
7	-14 + 12	12	21
8	12 + 21	33	33
9	33 - 1	32	33

---

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n = 0;
    int answer = 0;
    
    cin >> n;
    vector<int> arr = vector<int>(n, 0);
    vector<int> DP = vector<int>(n, 0);
    
    for(int i = 0; i < n; ++i)
        cin >> arr[i];
    
    answer = arr[0];
    DP[0] = arr[0];
    
    for(int i = 1; i < n; ++i)
    {
        DP[i] = max(DP[i - 1] + arr[i], arr[i]);
        answer = max(answer, DP[i]);
    }
    cout << answer << endl;
    return 0;
}