[ALGOSPOT] LIS

algospot.com/judge/problem/read/LIS

algospot.com :: LIS

<문제>

어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다.

어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라.

어떤 수열의 각 수가 이전의 수보다 클 때, 이 수열을 순증가 한다고 한다.

<입력>

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열에 포함된 원소의 수 N (<= 500) 이 주어진다. 그 다음 줄에 수열이 N개의 정수가 주어진다. 각 정수는 1 이상 100,000 이하의 자연수이다.

<출력>

각 테스트케이스마다 한 줄씩, 주어진 수열의 가장 긴 증가 부분 수열의 길이를 출력한다.

 

<구현>

O(N^2) LIS 로 구현

1. 완전탐색으로 답을 구함.

2. 앞으로 남은 선택들에 해당하는 점수만 반환

3. 재귀호출, 메모이제이션

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int n;
// O(n^2) LIS
int LIS(int k, vector<int>& v, vector<int>& dp)
{
    int& ret = dp[k];
    if(ret!=-1) return ret;
    ret = 1;
    for(int i=k+1;i<=n;i++)
        if(v[k]<v[i]) ret = max(ret, LIS(i, v, dp)+1);
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int tc;
    cin>>tc;
    while(tc--)
    {
        cin>>n;
        vector<int> v(n+1), dp(n+1, -1);
        for(int i=1;i<=n;i++)
            cin>>v[i];
        v[0] = INT_MIN;
        cout<<LIS(0, v, dp)-1<<endl;
    }
    return 0;
}