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

1912번: 연속합 (acmicpc.net)

1912번: 연속합

---

[백준/BOJ] 1912번 연속합 (C/C++) (tistory.com)

[백준/BOJ] 1912번 연속합 (C/C++)

- 동적 계획법 = 기억하며 풀기 

- n번까지의 연속합의 최대값은 [n-1번까지의 최대값 + n번 값] or [n번 값] 둘 중 큰 값이다.

 

 

 

 

---

#include <iostream>
using namespace std;

#define max(x,y) x > y ? x : y

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

	int ret = arr[0];
	dp[0] = arr[0];

	for (int i = 1; i < n; ++i) {
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);
		ret = max(dp[i], ret);
	}

	cout << ret << "\n";

	return 0;
}