[BOJ] 1912 연속합

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

Note

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

예제만 보고 양수의 합을 구하다가 다음 수가 음수가 나오면 현재 까지의 합을 남기는 알고리즘을 만들었다가
오답 한개를 추가하고 시작했다.

위 예제에서 -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;
}

2019-01-14 12:00:00에 Tistory에서 작성되었습니다.