[DP] BOJ 1912 연속합 - 오답노트

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

1912번: 연속합

 

- 문제 파악

주어진 수열에서 1개 이상의 연속되는 수를 선택하여 선택한 수들의 합의 최댓값을 출력하라.

 

- 나의 접근

i 번째 부터 n번째 모두 더하는데 그중에 가장 큰 값을 D 배열에 넣어놨다.

일단 위와 같은 경우는 시간 초과에 당연히 걸리며, 점화식을 전혀 활용하지 못했다.

for문을 한번만 사용해야한다는 것 까지는 깨달았지만, D를 어떤 식으로 사용해야할지 더 이상 생각나지 않았다.

 

- 정답

DP 문제는 의외로 간단하게 문제 풀리는데, 그게 더 맥빠진다.

 

D 배열은 수열의 값을 더한 결과를 입력하는데, 대신 D배열 + 현재값이 현재값보다 작으면 현재값부터 다시 시작한다.

 

#include "bits/stdc++.h"

using namespace std;

int n;
int D[100001];
int arr[100001];
int ans = -10000;

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

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	for (int i = 1; i <= n; i++)
	{
		if (D[i-1] + arr[i] < arr[i])
		{
			D[i] = arr[i];
		}
		else
		{
			D[i] = D[i - 1] + arr[i];
		}

		ans = max(ans, D[i]);
	}

	cout << ans;

}