https://www.acmicpc.net/problem/1912
#include <iostream>
using namespace std;
int dp[100001] = { 0 };
int input[1000001] = { 0 };
int max_val = -1001;
int main(void)
{
int N;
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> input[i];
}
for (int i = 1; i <= N; i++)
{
dp[i] = max(input[i], dp[i - 1] + input[i]);
max_val = max(max_val, dp[i]);
}
cout << max_val;
return 0;
}