[C++] 백준 1912번 연속합

 

1) 문제설명

백준 Online Judge 1912번 연속합

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

1912번: 연속합

 

2) 해결방법

 

입력값 :

2 -> 최대 2

2, 1 -> 최대 2+1 =3

2, 1, -4 -> 최대 2+1 =3

2, 1, -4, 3 -> 최대 2+1 =3 or 3

2, 1, -4, 3, 4 -> 최대 3+4 =7

이와 같이 생각했을 때 (지금까지 입력받았던 합중 최댓값) vs (새로 입력받은 숫자) 중 큰 것으로 dp를 설계하면 된다.

 

3) 코드

#include<iostream>
#include<queue>
#include<string.h>
#include<math.h>
#include<cmath>
#include<algorithm>

using namespace std;

int dp[1000001];

/*
연속합
해결방안
dp[] : 숫자들을 연속해서 하나씩 더한 것 vs 새로운 숫자


*/

int main() {
	int n, sum = 0;
	int arr[100001];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	
	dp[0] = arr[0];
	int maxt = arr[0];
	for (int i = 1; i < n; i++) {
		
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);
		if (dp[i] >  maxt) {
			maxt = dp[i];
		}
	}
	cout << maxt;
}

 

DP의 점화식을 세우는 것이 쉽지 않다.