BOJ 1912번 :: 연속합

#문제

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

1912번: 연속합

 

#작성 코드

#include <iostream>
#include <vector>
using namespace std;
 
const int MAX = 100000;
int n;
int sum[MAX];
int serial[MAX];
 
void input(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>serial[i];
    }
}
 
int solve(){
    // 첫 번째 원소로 가장 큰 연속합, 첫 번째 연속합 초기화. 
    int sumMax=serial[0];
    sum[0] = serial[0];
    for(int i=1; i<n; i++){
        // '현재 원소 < 이전 연속합 + 현재원소' 일 때 더 큰 것을 sum[i]로 저장. 
        sum[i] = max(sum[i-1]+serial[i], serial[i]);
        // 가장 큰 연속합을 갱신한다. 
        sumMax = max(sumMax, sum[i]);
    }
    return sumMax;
}
 
int main(){
    input();
    cout<<solve();
    return 0;
}

##

처음에 2차원 DP를 사용해서 풀려고 코드를 작성했는데,

int sum[100000][100000]; 으로 sum 배열을 선언하고 컴파일하니 컴파일 에러가 발생했다.

구글링해보니, 4*10^10Byte -> 4GB라서 배열의 사이즈가 너무 커서 문제가 생긴것이었다.