백준 1912. 연속합 (DP)

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

1912번: 연속합

n이 1<=n<= 10^5이다. 가장단순한 이중 for문으로 풀 수 없다. 

이 문제를 잘 이해하면, 이 전에 연속된 값들에 현재값을 더한 값이 현재값만 있을 때 보다 크다면 계속해서 그 값에 현재값을 더해주고, 그렇지 않다면 현재값부터 다시 시작하다고 생각할 수 있다. 

 

예를 들어  2 1 -4 3 인 수열이 있을 때 

2, 3(2+1), -1(3+(-4)), 3(-1+3 < 3)이다.

 

이를 코드로 구현하면 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <limits.h>
#include <algorithm>
using namespace std;

int n;
int arr[100002];
int d[100002]; //i좌표까지의 최댓값
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i];   
    }

    d[1] = arr[1];

    for(int i = 2; i <=n; i++)
    {
        d[i] = max(d[i-1]+arr[i], arr[i]);
    }

    cout << *max_element(d+1, d+n+1);

}