[백준 1912] 연속합

분류 : dp

 

요구사항

주어진 수열 중 연속으로 이루어진 수열의 최대 값 구하기

 

풀이

현재 값이 최대일 경우는 두가지이다

1. 이전 값들의 합과 현재 값 더했을때

2. 현재 값

둘 중 하나가 최대 값이다

점화식은 다음과 같이 된다

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

 

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

int map[100100];
int d[100100];
int n;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &map[i]);
	}
	int ans = 0;
	d[1] = map[1];
	ans = map[1];
	for (int i = 2; i <= n; i++) {
		d[i] = max(d[i - 1] + map[i], map[i]);
		ans = max(ans, d[i]);
	}
	cout << ans << endl;
}