어떤 수열이 있을 때 연속된 구간의 최대합을 출력하려고 한다.

예를 들어

2 -6 4 5 -2 6 2 -1이라는 수열이 있다면 

연속된 구간의 최대 부분합은 15이다. (4+5+ -2 + 6 + 2)

입력

첫째줄에 수열의 원소의 개수 n이 입력된다. (1 <= n <= 100,000)

둘째 줄에 n개의 정수 원소 값이 차례대로 입력된다. (값의 범위: -100 ~ + 100)

출력

연속된 구간의 최대합을 출력한다.

입력 예시

8 2 -6 4 5 -2 6 2 -1

출력 예시

15




일단 입력이 10만개라서... 2차원 배열은 못했구요
그래서..


#include<iostream>

using namespace std;
int data[100001] = { 0, };
int main() {
int N = 0, before = 0, big = 0;
cin >> N;

for (int i = 0; i < N; i++) 
cin >> data[i];
before = data[0];

for (int i = 0; i < N-1; i++) {
before = data[i];
for (int j = i + 1; j < N; j++){
before = before + data[j];
if (before >= big)
big = before;
}
}
cout << big << endl;
return 0;
}


이렇게 풀었는데... (피보나치 수열 풀듯이... )
그런데 시간초과가 나더라구요...
접근은 어떻게 해야될까요??
(DP 로 접근해주세요)