최장 증가 부분 수열 DP O(N^2)

백준 : https://www.acmicpc.net/problem/11053

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

 

 오늘은 DP를 이용해 최장 증가 부분 수열의 길이를 구하는 코드를 구현해볼 것이다.

최장 증가 부분 수열 : 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.
ex)  A = {10, 20, 10, 30, 20, 50} 일 떄 10,20,30,50. , 길이 4

 

먼저 DP[i]를 정의하자.

DP[i] = |수열의 i번째 원소를 포함하는 i번째 원소까지의 최장 증가 부분 수열 길이|

 

i번째 원소를 포함할 때 이전까지의 최장 증가 부분 수열의 마지막 항이 i번째 원소보다 작았어야한다. 따라서 0번부터 i-1번의 원소 중 i번째 원소보다 작고, DP값이 가장 큰 원소를 골라주면 된다.

DP[i] = max(DP[a1],DP[a2],....,DP[am]) + 1    (단, i > aj && A[i] > A[aj])

 

이를 코드로 구현해보자.

#include <iostream>
using namespace std;

int dp[1001],num[1001];
int main()
{
    int N,mx=0;
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>num[i];
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=0;j<=i-1;j++)
        {
            if(num[i]>num[j])
            {
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
        if(mx < dp[i])
        {
            mx = dp[i];
        }
    }
    cout<<mx;
}

시간 복잡도 : O(N^2)