[백준 1912] 연속합

문제

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

 

입력

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

 

출력

가장 큰 합을 출력한다.

---

접근

반드시 하나의 수를 선택해야하고 연속된 수를 선택해야한다.

동적계획법으로 접근을 해본다면 현재까지 연속적으로 선택한 수의 합과 현재의 수를 비교해서 최댓값을 기록해둔다.

기록된 공간에는 현재의 수까지 연속적으로 선택한 꼴이된다.

 

만약 1 2 3 4 5의 위치에 있는 수가 있다고 하면

1, 2까지 선택을 하고 3을 선택하려고할 때 1, 2, 3에 있는 수를 더한 것보다 3혼자 선택한 것이 더 클 때 3을 선택한다. 이후 4를 선택할 때도 마찬가지로 이전의 수까지 기록된 최댓값을 활용하여 3+4 또는 4를 선택하게 된다.

이런식으로 진행하면 기록해둔 값은 연속적으로 선택했다고 할 수 있고 현재의 수를 더할 것인지 아니면 더하않고 독자적으로 선택할지를 결정하면된다.

 

구현

처음 answer에는 첫 번째 위치에 있는 수를 저장하도록 하고 기록해두는 공간인 dp의 첫 번째에도 첫 번째 수를 기록한다. 이어서 두 번째 수부터 탐색을 하여 이전의 수와 합칠지, 아니면 합치지않고 해당 수만 선택할지를 최댓값비교를 통해 선택을 한다.

그리고 매번 answer와 현재까지 기록한 수를 비교하여 최댓값을 찾는다. 기록해두는 dp 끝에 최댓값이 저장되는 것이 아니다.

	int answer = numbers[0];
	dp[0] = numbers[0];
	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i - 1] + numbers[i], numbers[i]);
		answer = max(answer, dp[i]);
	}

---

전체 코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;


int main()
{
	int n;
	int numbers[100000];
	int dp[100000];
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &numbers[i]);
	}

	int answer = numbers[0];
	dp[0] = numbers[0];
	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i - 1] + numbers[i], numbers[i]);
		answer = max(answer, dp[i]);
	}

	cout << answer << endl;
	return 0;
}