백준 1912: 연속합

문제 요약

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

문제 분류

• 다이나믹 프로그래밍

문제 풀이

i번째의 수를 v[i], i번째의 수를 포함한 수열의 최대합을 dp[i]라고 하자.

이렇게 놓았을때 dp[i]는 반드시 v[i]를 포함하게 되는데, 이때 수열이 반드시 연속해야하므로 두가지 경우가 생긴다. 이전 수열에 이어서 v[i]를 넣느냐, 다시 v[i]부터 새로운 수열을 만드느냐.

그 두 가지 경우를 비교하여 최댓값을 찾으면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dp[100001];

int main()
{
	int n, input, res;
	vector<int> v;

	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d", &input);
		v.push_back(input);
	}
	dp[0] = v[0];
	res = dp[0];
	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i - 1] + v[i], v[i]);
		res = max(res, dp[i]);
	}
	cout << res;
}