[백준 C++] 1912 연속합 - 다이나믹프로그래밍

1912번: 연속합

#include <iostream>
#include <vector>
using namespace std;

vector<int> DP;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N;
	cin >> N;
	DP.reserve(N);

	int Num;
	cin >> Num;
	DP.emplace_back(Num);

	int Max = Num;
	for (int i = 1; i < N; ++i)
	{
		cin >> Num;
		Num = max(Num, DP[i - 1] + Num);
		DP.emplace_back(Num);

		Max = max(Max, Num);
	}

	cout << Max;
}

---

 

1~N 사이의 구간합 중 최대값을 출력하는 DP 유형의 문제입니다.

풀이 과정은 간단합니다.

 

N개의 수를 입력받을 때 DP 배열에 해당 수 또는 해당 수를 포함한 이전 수들과의 구간합 중에서 큰 수를 저장해줍니다.
DP 배열을 모두 채운 후에는 그 중 가장 큰 값을 출력해주면 됩니다.