[BOJ 1912] 연속합

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

1. dp를 통해 합을 구한다.

2. 최대 크기에 유의한다.

#include <iostream>

#include <algorithm>

using namespace std;

#define MAX_N 100001

int i, N;

int a[MAX_N], dp[MAX_N], result;

void input()

{

cin >> N;

for (i = 1;i <= N;i++)

{

cin >> a[i]; dp[i] = 0;

}

}

void cal()

{

dp[0] = 0; result = -1001;

for (i = 1;i <= N;i++)

{

if (dp[i - 1] + a[i] >= a[i]) dp[i] = dp[i - 1] + a[i];

else dp[i] = a[i];

result = max(result, dp[i]);

}

}

int main()

{

input(); cal();

cout << result << endl;

}