백준 1912 - 연속합

문제

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

1912번: 연속합

 

 

풀이

n번째 숫자에서 발생하는 비교 연산은 다음과 같다.

( n - 1 번째 숫자까지의 최대값 + arr[n] ) ,  arr[n]

두 숫자 중 큰 값이 n번째 숫자에서의 최대값이 된다.

 

d[n] = arr[n]을 포함하는 연속된 수열 중 최대값 이라고 하면

다음의 점화식을 구할 수 있다.

d[n] = max {

  ( d[n-1] + arr[i] ), arr[i]

}

 

 

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n;
int arr[100001];
int dp[100001];
int result;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    for (int i = 1; i <= n; i++)
    {
        dp[i] = arr[i];
        if (arr[i] + dp[i - 1] > dp[i]) dp[i] = arr[i] + dp[i - 1];
    }
 
    result = dp[1];
    for (int i = 2; i <= n; i++) result = max(result, dp[i]);
    cout << result;
 
    return 0;
}