[210528][백준/BOJ] 1912번 연속합

문제

입출력

풀이

그전까지 더해온 값+자신을 더한 값과 자신의 값을 비교해서 최대값을 구하는 방식으로 문제를 풀었다.
점화식은 다음과 같다.

d[i] = max(d[i-1]+A[i], A[i]);

코드

#include <bits/stdc++.h>
using namespace std;

int d[100002];
int A[100002];

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


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

	int n;
	cin >> n;

	for (int i = 1; i <= n; ++i)
		cin >> A[i];

	cout << dp(n);
}