[백준][DP] 연속합

1. 문제 주소

1912번: 연속합

2. 문제

연속된 숫자들의 합 중에서 가장 큰 합을 구하는 문제이다. 숫자를 더해나가다가 음수를 만났을 때 이전의 연속합에 더할지 아니면 버리고 새로 시작할지를 생각하면 쉽게 풀 수 있는 문제이다.

3. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<int> sum(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < n; i++) {
        sum[i] = arr[i];
        if (i == 0) continue;
        sum[i] = max(sum[i - 1] + arr[i], sum[i]);
    }
    cout << *max_element(sum.begin(),sum.end());
    return 0;
}