[백준 DP] 1912번 - 연속합

1912번 - 연속합

---

<문제>

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

1912번: 연속합

 

<문제 풀이>

초기 dp 배열

계산 과정

완성된 dp 배열

완성된 dp 배열에서 최댓값을 출력하면 문제에서 찾는 답이 된다. 

점화식: dp[i] = dp[i] + dp[i-1], dp[i] = arr[i]

 

<코드>

#include <iostream>
using namespace std;

int n;
int dp[100001] = { 0, };
int arr[100001] = { 0, };

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> dp[i];
		arr[i] = dp[i];
	}

	int m = dp[1];
	for (int i = 2; i <= n; i++) {
		if (dp[i] > (dp[i - 1] + dp[i])) {
			dp[i] = arr[i];
		}
		else {
			dp[i] += dp[i - 1];
		}

		if (m < dp[i]) m = dp[i];
	}

	/*for (int i = 1; i <= n; i++) {
		cout << dp[i] << " ";
	}
	cout << endl;*/

	cout << m << endl;

	return 0;
}

 

 

 

2022.11.25