득이공간

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

PS/알고리즘 문제풀이

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

쟁득 2024. 3. 5. 08:58
 

1912번: 연속합

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

www.acmicpc.net

#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 배열을 모두 채운 후에는 그 중 가장 큰 값을 출력해주면 됩니다.