Coding Test - cpp/DP
[백준 1912: 연속합] - C++
에드윈H
2021. 1. 22. 22:03
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
cin >> n;
int arr[100001];
int dp[100001];
int input;
for (int i = 0; i < n; i++)
{
cin >> input;
arr[i] = input;
dp[i] = input;
}
int result = dp[0];
for (int i = 1; i < n; i++)
{
dp[i] = max(dp[i], dp[i - 1] + arr[i]);
if (result < dp[i])
result = dp[i];
}
cout << result << endl;
return 0;
}