백준 1912 : 연속합 c++ 정답 (배열 이용)

https://github.com/o920/baekjoon/blob/master/1912.cpp

o920/baekjoon

1. n입력받고 배열 입력받음

2. dp 배열에 dp 채움

3. dp 채우는 방법은 자기 직전 연속합최대와 자신의 합 vs 자신만 있을 때 중 큰 걸로 결정

 

#include <iostream>
#include <algorithm>
using namespace std;
int N[100000];
int dp[100000];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> N[i];

	dp[0] = N[0];
	int result = dp[0];
	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i - 1] + N[i], N[i]);
		result = max(result, dp[i]);
	}
	cout << result << endl;
}