[c++] 백준 1912 연속합

#include<iostream>
#include<algorithm>
using namespace std;

int arr[100000];
int dp[100000];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	//dp는 
	dp[0] = arr[0];  //기본적으로 첫번째 인덱스는 같다, 먼저 초기화해주기
	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);
	}
	
	int Max = dp[0];  //입력조건을 보고 나올 수 없는 수 중에서 가장 작은수로 초기화하기 or 현재 dp배열에서 가장 작은수
	
	for (int i = 0; i < n; i++)
		if (Max < dp[i])
			Max = dp[i];

	cout << Max;
}