c++ 백준 1912번 문제

[Silver II] 연속합 - 1912

문제 링크

성능 요약

메모리: 2928 KB, 시간: 8 ms

분류

다이나믹 프로그래밍

문제 설명

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

풀이

1. 값이 모두 음수일때와 섞여있을때를 flag를 사용해 나누어 계산했다.
2. 값이 양수일때 sum에 값을 더하고, 음수가 나올때 dp에 값을 넣었다.
3. sum이 0보다 작아질 경우에는 0으로 초기화 후 그 다음 연산부터 시작한다.
4. dp에 들어간 값을 오름차순으로 정렬하고 dp[0] 값을 가져온다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int arr[100001];
vector<int>	Dp;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	vector<int> Dp;
	int n;
	cin >> n;
	int sum = 0;
	int m_max = -1001;
	bool flag = false;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i] > 0&&!flag) {
			flag = true;
			sum = 0;
		}
		else if(!flag)
		{
			if (m_max < arr[i])
				m_max = arr[i];
		}
		if (flag) {
			if (arr[i] > 0)
				sum += arr[i];
			else if (arr[i] <= 0) {
				Dp.push_back(sum);

				sum += arr[i];
				if (sum < 0)
					sum = 0;
			}
			if (i == n - 1)
				Dp.push_back(sum);
		}
	}

	if (flag)
	{
		sort(Dp.begin(), Dp.end(),greater<int>());
		cout << Dp[0];
	}
	else
		cout << m_max;

}

Dp 활용 풀이

#include <iostream>

using namespace std;
int main()
{
	int n,res,a[100001],dp[100001];
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	res=a[1];
	dp[1]=a[1];
	for(int i=2;i<=n;i++)
	{
		dp[i]=max(dp[i-1]+a[i],a[i]);
		res=max(dp[i],res);
	}
	cout<<res;
}