[백준,c++] 1912번 - 연속합

문제

1912번: 연속합

 

코드

#include <iostream>

using namespace std;

int arr[100001];
int dp[100001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin>>n;
    
    for(int i=0; i<n; i++) cin>>arr[i];
    
    dp[0] = arr[0];
    int ans = dp[0];
    for(int i=1; i<n; i++){
        dp[i] = max(arr[i], dp[i-1]+arr[i]);
        ans = max(ans, dp[i]);
        
    }
    
    cout<<ans;
}

 

풀이(7분)

(현재 배열의 값 vs 이전까지의 합 + 현재 배열) 중 큰 값을 계속 메모이제이션 하면서 결괏값을 구해 낼 수 있습니다.