[백준 1912] 연속합 (DP) (C/C++) (★)

#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int Max = -99999999;
int arr[100010];
int dp[100010];
 
int solve(int cnt)
{
    if(cnt == 0)
    {
        return 0;
    }
    
    if(dp[cnt] != -1111)
    {
        return dp[cnt];
    }
    
    dp[cnt] = arr[cnt];
    dp[cnt] = max(dp[cnt], dp[cnt] + solve(cnt-1));    
    
    return dp[cnt];
}
 
int main(void)
{
//    freopen("B1912_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> arr[i];
        dp[i] = -1111;
    }
    
//    for(int i = N; i >= 1; i--)
//    {
//        Max = max(Max, solve(i));    
//    }
 
    solve(N);
    for(int i = 1; i <= N; i++)
    {
        if(Max < dp[i])
        {
            Max = dp[i];
        }
    }
    
    cout << Max;
    
    return 0;
}