[백준 / BAEKJOON] 1912번 연속합 - C++

문제 원문

조건

시간 제한 : 1초
메모리 제한 : 128 MB

문제

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

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제

풀이

양수가 나오면 더하고 음수가 나오면 초기화 하는 그리드 알고리즘으로 풀면 최댓값이 나오지 않는 경우가 있기 때문에 동적계획법으로 풀었습니다.

점화식은

DP[i] = max(Arr[i], Arr[i] + DP[i-1])

입니다.

현제값이 누적한 값보다 크다면 더할 이유가 없기 때문에 누적해서 더하지 않고 현제값으로 초기화하여 최댓값을 구합니다.

성공 코드

#include <vector>
#include <iostream>
#include <limits>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

int main()
{
	int nSize;
	cin >> nSize;
	vector<int> vArr(nSize);
	vector<int> vDp(nSize);
	for (int i = 0; i < nSize; i++)
	{
		cin >> vArr[i];
	}

	int nMax = vArr[0];

	vDp[0] = vArr[0];

	for (int i = 1; i < nSize; i++)
	{
		vDp[i] = max(vArr[i], vArr[i] + vDp[i - 1]);
		if (nMax < vDp[i])
			nMax = vDp[i];
	}

	cout << nMax << '\n';

	return 0;
}

결과

Github - github.com/ledpear