[백준/BOJ] 1912번 연속합 (C++)

www.acmicpc.net/problem/1912

1912번: 연속합

DP 유형의 문제입니다.

n까지 연속되는 합을 더해가다가 0보다 작아졌을 때는 0으로 초기화 후 연속합을 구하는게 포인트입니다. 따라서 이를 점화식으로 나타내면 다음과 같습니다.

 

dp[n] = max(0, dp[n - 1]) + v[n]

 

마지막으로 1~n까지 각 구간에서의 합 중 최대값을 출력하면 됩니다. 

 

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

int dp[100001];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin>>n;
    vector<int> v(n + 1);
    for(int i = 1; i <= n; i++) {
        cin>>v[i];
    }
    
    // 초기값 설정
    dp[1] = v[1];
    
    // 연속되는 합이 0이 될때는 0으로 초기화 되도록 점화식 설정
    for(int i = 2; i <= n; i++) {
        dp[i] = max(0, dp[i - 1]) + v[i];
    }
    
    cout<<*max_element(dp + 1, dp + n + 1);
}