[백준,c++] 1912번

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

dkswnkk 2022. 3. 15. 01:32

문제

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

코드

#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 이전까지의 합 + 현재 배열) 중 큰 값을 계속 메모이제이션 하면서 결괏값을 구해 낼 수 있습니다.

저작자표시 (새창열림)