[백준][1912번] 연속합

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

1912번: 연속합

 

풀이과정

 

연속 된 부분 수열 중 최대값을 구하는 문제이다.

 

dp[N] 에는 map[1] ... map[N]까지의 합 또는 map[N]값중 더 큰 값을 저장시켰다. 

 

dp[N-1]이 음수인 경우 map[N]이 더 크기 때문이다. (if map[N] > 0)

 

dp[N] = max((dp[N-1] + map[N]) , map[N]) 과 같은 점화식을 구 할 수 있었다.

 

소스코드

#include <stdio.h>

int dp[100001];
int map[100001];
int N;
int solution()
{
	int answer = map[0];
	dp[0] = map[0];
	for (int i = 0; i < N; i++) {
		dp[i] = map[i];
		if (dp[i - 1] + dp[i] > dp[i]) {
			dp[i] = dp[i] + dp[i - 1];
		}
		if (answer < dp[i]) {
			answer = dp[i];
		}
	}
	return answer;
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &map[i]);
	}
	printf("%d\n", solution());
}