[백준] 1912 연속합

DP 문제들은 문제를 풀 수록 어렵네;

점화식 찾기가 너무 어려워ㅓㅓ

 

최대값을 구하는 방법으로 입력받은 값 array[i]과 이전까지의 값(dp[i-1])을 비교하여 큰 값을 dp[i]에 저장하면 된다.

 

#include <bits/stdc++.h>
using namespace std;

void yeun1912(){
    int n;
    scanf("%d",&n);
    int array[100'001];
    int dp[100'001];
    
    for(int i=0;i<n;i++){
        int num;
        scanf("%d",&num);
        array[i] = num;
    }
    
    dp[0] = array[0];
    int ans = dp[0];
    
    for(int i=1;i<n;i++){
        dp[i] = max(array[i], dp[i-1] + array[i]);
        
        if(ans < dp[i])
            ans = dp[i];
    }
    printf("%d\n",ans);   
}