[주의][다이나믹 프로그래밍] 연속합

문제 링크 : https://www.acmicpc.net/problem/1912

연속합 성공 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 33191 8886 6170 26.961% 문제 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  10 10 -4 3 1 5 6 -35 12 21 -1 예제 출력 1  33

[ 문제 풀이 ]

D[i] = A[i]가 마지막으로 온, 연속된 숫자합 중 가장 큰 합.

D[i]에 올 수 있는 경우는 두가지 경우이다.

연속합이랬으므로,

① 양수라서, 지금까지의 값을 더하는게 이득일 경우 D[i] = D[i-1] + A[i]

② 음수라서, 지금까지의 값을 버리고 새로 시작하는게 이득일 경우 D[i] = A[i]

따라서, D[i] = max(D[i-1] + A[i], A[i])

※ 절대 주의! 최대값/최소값에서 음수를 다루는 경우 result 변수의 초기값 Setting에 유의해야한다.

int result = -1001; // 음수일 때, min값 처리에 주의!(문제에서 최소값 -1000으로 줬음)

...

for (register int i = 1; i <= N; i++)
	result = MAX(result, D[i]);

[ 최종 구현(C++) ]

#include <stdio.h>
#define MAX_NUMBER 100002
#define MAX(a,b) ((a) > (b) ? (a) : (b));

int D[MAX_NUMBER] = { 0, };
int A[MAX_NUMBER] = { 0, };

int main(void)
{
	int N;
	int result = -1001; // 음수일 때, min값 처리에 주의!(문제에서 최소값 -1000으로 줬음)

	scanf("%d", &N);

	for (register int i = 1; i <= N; i++)
		scanf("%d", &A[i]);
	
	D[1] = A[1];

	for (register int i = 2; i <= N; i++) {
		/*
		// D[i] = 0으로 초기화하면 음수랑 비교할경우 
		아무 의미없는 0값이 최대값으로 나오는 현상 방지하기 위해 
		초기화를 선택지값 중 하나로 해버림.
		*/
		D[i] = A[i];
		D[i] = MAX(D[i - 1] + A[i], D[i]);
	}

	for (register int i = 1; i <= N; i++)
		result = MAX(result, D[i]);

	printf("%d\n", result);

	return 0;
}