[C++] 백준 1912번 - 연속합

DP를 사용하는 문제

DP의 합과 입력받은 arr의 숫자를 잘 비교하면 되는 것 같다.

 

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

int arr[100001]{ 0, };
int dp[100001]{ 0, };

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

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

	dp[1] = arr[1];
	int result = dp[1];

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

	cout << result << "\n";

	return 0;
}