[C언어] 백준 1912 : 연속합

생각의 흐름

처음엔 그냥 마이너스있으면 다 0으로 초기화시키면서 sum에 저장하며 max를 찾아주면 되겠구나 싶었다. 뭐 굳이 dp 써야되나? 싶었다 이게 dp인가? 모르겠다.
그래서 일단 양수의 합만 체크하는걸로 코드를 작성했다.

예제1에 12와 21을 더한 최댓값 33은 잘 나왔지만, 예제2에서 최댓값이 11이 나왔다. 이유는 3 + 4 - 4 + 6 + 5 로 마이너스가 있어도 계산을 해주어야 한다.
아 그러면 내가 위에 적은 값과 비교해서 max값인걸로 출력하면 끝나겠구나 생각했다.

예제2를 어떤식으로 생각했냐면, 똑같이 sum에다 숫자를 하나씩 더해주면서 진행한다. 바로바로 max체크를 해주면서 진행한다. 그러다가 sum이 음수가 되는경우, 앞에있는 연산은 다 버린다. 왜냐하면 앞에있는걸 챙겨가면 무조건 손해를 보기 때문이다.
그렇게 음수가 나오면 0으로 초기화하고, 진행하며 max를 찾아준다.

맨 위에서 정한 max값과 방금정한 max1값을 비교해서 최댓값을 출력하면 끝이다.

내가 푼 코드

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

int main()
{
	int i, n;
	int arr[100001];
	int sum = 0, max = -1001;
	int result;
	scanf("%d", &n);
	i = 0;
	while (i < n)
	{
		scanf("%d", &arr[i]);
		i++;
	}
	i = 0;
	while (i < n)
	{
		if (arr[i] > 0)
		{
			sum = sum + arr[i];
			if (max < sum)
			{
				max = sum;
			}
		}
		else if (arr[i] < 0)
		{
			sum = 0;
		}
		i++;
	}
	i = 0;
	sum = 0;
	int max1 = -1001;
	while (i < n)
	{
		sum = sum + arr[i];
		if (max1 < sum)
		{
			max1 = sum;
		}
		if (sum < 0)
		{
			sum = 0;
		}
		i++;
	}
	result = MAX(max, max1);
	printf("%d", result);
}