[C++] 백준 1912 - 연속 합

문제 링크

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

연속되는 값들의 합 중 최대값이기 때문에

이전부터 현재까지 연속되는 값과 현재부터 이후로 연속되는 값을 구해나가야 합니다. 

따라서 직전 위치의 최대값+현재값과 현재값 중 더 큰 값을 배열에 저장합니다.

그리고 배열의 값 중 최대값을 구하면 됩니다.

 

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	using namespace std;
	int num[100001];
	int dp[100001];
	int main()
	{
	int n;
	int sum;
	cin >> n;
	for (int i = 0; i < n; i++)
	cin >> num[i];
	dp[0] = num[0];
	sum = num[0];
	for (int i = 1; i < n; i++){
	dp[i] = max(dp[i - 1] + num[i], num[i]);
	sum = max(sum, dp[i]);
	}
	cout << sum << endl;
	return 0;
	}

view raw 1912.cpp hosted with ❤ by GitHub