[백준/C++] 11055번 - DP (설명 포함)

 

 

 

예시로 이해하기

i는 인덱스로 1부터 잡았고,

a[i]는 입력되는 값이다.

d[i]는 i까지 커지는 부분 수열 합의 최대 값이다.

 

i번째 숫자마다 처음부터 자기자신 (i-1)전까지 숫자를 확인하면서

자기보다 작다면 부분수열로 넣을지 말지 판단하면 되는데, 이 때 max를 이용해서 큰 수가 되도록 유지해야한다. 

 

아래 예시를 통해 한 번 이해해보자.

 

 

 

코드

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

int n;
int a[1002];
int d[1002];
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    
    for (int i=0;i<n;++i) cin>>a[i];

    for (int i=0;i<n;++i){
        d[i]=a[i];
        for (int j=0;j<i;++j){
            if (a[j]<a[i]) {
                d[i]=max(d[j]+a[i],d[i]);
            }
        }   
    }
    
    cout<<*max_element(d,d+n);
}