[백준] 11053번 가장 긴 증가하는 부분 수열 (C)

문제 주소

백준 11053번 가장 긴 증가하는 부분 수열

불러오는 중입니다...

알고리즘

DP

힌트

dp배열에 i번째 수 까지 가장 긴 증가하는 부분 수열의 길이를 저장한다.

문제풀이

i번째 수 까지 가장 긴 증가하는 부분 수열의 길이를 구하기 위해선 i번째 이하의 1~i-1의 구간의 수를 j라 할 때
in[i]가 in[j]보다 크다면 dp[j]+1, 작다면 dp[j]를 선택한 값의 최대값을 구하면 된다. 답은 dp[1]~dp[n]까지의 수 중 최대값이다.

#include<iostream>
using namespace std;
int dp[1001];
int in[1001];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>in[i];
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++){
            if(in[j]<in[i])
                dp[i]=max(dp[i],dp[j]+1);
        }

        ans=max(dp[i],ans);
    }

    cout<<ans;
}