[알고스팟 LIS] Longest Increasing Sequence C++

algospot.com/judge/problem/read/LIS

algospot.com :: LIS

난이도하인데 어려웠음...

 

부분 최적에 대한 부분도 조금 난해한 문제

알고리즘은 start 이후에 나오는 arr[start]보다 큰 수를 가진 부분증가수열을 찾으며

가장 큰 길이가 나오는것들을 찾는 방식

어렵다 ㅜㅜ 난이도 하 맞냐

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> arr(501);
int dp[501];
int n;
 
int lis(int start) {
    int& ret = dp[start+1];
    if (ret != -1) return ret;
 
    ret = 1;
 
    for (int i = start + 1; i < n; i++)
        if (start==-1 || arr[start] < arr[i])
            ret = max(ret, lis(i) + 1);
 
    return ret;
    
}
int main() {
    int c;
    cin >> c;
    while (c--) {
        memset(dp, -1, sizeof(dp));
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> arr[i];
 
        cout << lis(-1)-1 << '\n';
    }
    return 0;
}