백준 1912 C언어

생각을 하면 매우 쉬운 문제이다. 하지만 나는 잘 떠오르지 않았다....

이 문제는 DP문제의 본질을 생각하면 풀리는 것 같다. DP는 전에 있던 결과 값을 활용하여

큰 문제를 작은 문제로 나누어 가지로 뻗어 나가는 느낌이다.

내가 푼 코드는 if (arr[i - 1] > 0) 이 부분이 가장 중요하다

전에 값인 arr[i-1]이 0보다 크면 현재의 arr[i] 값과 더하는 arr[i] = arr[i] + arr[i-1]을 해주면 된다.

어차피 전에 값이 양수이면 더하면 더 크다. 

즉 전에 값이 양수이면 현재 값에 더해준다. 이것이 핵심 알고리즘이다.

 

#include<stdio.h>

int main() {

	int arr[100001];
	int n;
	int max;

	scanf("%d", &n);

	scanf("%d", &arr[0]);
	max = arr[0];

	for (int i = 1; i < n; i++) {
	
		scanf("%d", &arr[i]);
		if (arr[i - 1] > 0)
			arr[i] = arr[i] + arr[i - 1];

		if (max < arr[i])
			max = arr[i];
	
	}

	printf("%d", max);

	return 0;
}