[1912] 연속합

풀이

dp[i] = i번째 값을 포함하는 가장 큰 연속합

정답 : dp[1:n] 중 가장 큰 값

dp[i] = max(dp[i-1] + v[i], v[i])

현재 값을 포함해서 가장 많이 연속해서 더한 것보다, 지금 하나만 더한 것이 더 큰지 아닌지 판단.

코드

#include <cstdio>
#include <algorithm>
using namespace std;
int v[100001];
int dp[100001];
int n;

int main(void) {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &v[i]);
		dp[i] = v[i];
	}
	
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + v[i] > v[i] ? dp[i - 1] + v[i] : v[i];
	}
	printf("%d\n", *max_element(dp + 1, dp + n + 1));

	return 0;
}