BaekJoon 1912 연속합

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

소스결과 2652 KB / 8 ms

출처 Backjoon

언어 C++ 17

분류 다이나믹 프로그래밍, 수학

 

설명

임의의 수열에 대해서 연속된 수의 합이 최대를 구하는 문제

 

예제만 보고 양수의 합을 구하다가 다음 수가 음수가 나오면 현재 까지의 합을 남기는 알고리즘을 만들었다가

오답 한개를 추가하고 시작했다.

 

위 예제에서 -35를 21 뒤에 놓는 형태로 바꾸면

문제에 숨겨진 함정이 나온다.

 

음수가 존재 한다고 해서 그 다음 수를 더했을 때 현재 까지의 합이 최대라는 보장이 없는 함정이 숨어 있다.

DP Table 조금 변형을 가해서 현재까지의 합 + 다음 수의 합이 음수가 된다면

음수의 그 다음수가 양수여도 현재 합을 넘을 수 없는 상황이 된다.

 

음수가 된다면 현재 까지의 합을 끊고 다음 위치부터 다시 구해야 한다.

 

따라서 점화식은 다음과 같다

if (dpTable[i - 1] < 0) ( 단 i > 0 )
	dpTable[i] = numbers[i];
else
	dpTable[i] = dpTable[i - 1] + numbers[i]; 

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

const int MAX = 100000;

int main()
{
	int n;
	int numbers[MAX + 1];
	int dpTable[MAX + 1];
	int max = 0;

	cin >> n;

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

	dpTable[0] = numbers[0];
	max = dpTable[0];

	for (int i = 1; i < n; i++)
	{
		if (dpTable[i - 1] < 0)
			dpTable[i] = numbers[i];
		else
			dpTable[i] = dpTable[i - 1] + numbers[i];
	}

	for (int i = 0; i < n; i++)
		if (max < dpTable[i])
			max = dpTable[i];

	cout << max;

	return 0;
}