[백준] 1912번 연속합

문제 링크: https://www.acmicpc.net/problem/1912

문제 및 입출력

문제 접근

DP 문제였다. 이전 까지 더한 값과 현재 값을 더한 값과 현재 값과의 크기를 비교하여, 큰 값이 현재까지의 연속된 수의 합 중 가장 큰 것이기 때문에 저장해준다.
dp[i] = max(dp[i-1] + num[i], num[i])

코드 구현(c++)

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int num[100001];
    int dp[100001];
    int N;
    cin >> N;
    for(int i = 0 ; i < N ; i++){
        cin >> num[i];
    }
    dp[0] = num[0];
    int result = dp[0];
    for(int i = 1 ; i < N ; i++){
        dp[i] = max(dp[i-1] +  num[i], num[i]);
        result = max(result, dp[i]);
    }
    cout << result << "\n";
}