(c++)백준 1912번: 연속합

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

1912번: 연속합

* 연속된 수를 선택해야 하며, 수를 한 개 이상 선택해야 한다. = 바로 직전 수까지의 연속합에 현재 값을 더하는 게 현재 값보다 큰지 비교하여 dp에 저장

 

※점화식※

dp[i] : i번째 수를 마지막으로 연속합에 포함시킬 때 나올 수 있는 가장 큰 값

dp[1] = A[1]

dp[x] = max(dp[x-1] + A[x], A[x])

 

#include <iostream>
#include <algorithm>//max
using namespace std;

int n;
long long dp[100001];
long long A[100001];

void DP() {
	long long Max = -10000;
	dp[1] = A[1];

	for (int i = 2; i <= n; i++) {
		//이전까지의 연속합에 현재 값을 더하는 거랑 그냥 현재값 중 더 큰 거
		dp[i] = max(dp[i - 1] + A[i], A[i]);
	}

	for (int i = 1; i <= n; i++) {
		Max = max(Max, dp[i]);
	}
	cout << Max << endl;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
	}
	DP();
	return 0;
}