[algospot] LIS

문제링크 입니다

[LIS] 문제

최대 증가 부분 수열 찾기.

입력 값은 다음과 같습니다

7
4
1 2 3 4
8
5 4 3 2 1 6 7 8
8
5 6 7 8 1 2 3 4
7
9 1 3 7 5 6 20
5
2 5 6 1 2
10
1 2 5 8 10 2 5 4 3 50
6
1 2 5 3 4 5

출력값은 다음과 같습니다.

4
4
4
5
3
6
5

전체 코드는 다음과 같습니다.

//
//  LIS.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/09/15.
//

#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream fin("LIS.txt");
int cache[501];
int sequence[501];
int num;
int LIS(int a){
    int &ret = cache[a+1];
    if(ret != -1) return ret;
    ret = 1;
    for(int i = a + 1; i < num; ++i){
        if(a == -1 ||sequence[a] < sequence[i])
            ret = max(ret, LIS(i) + 1);
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    int Test_case;
    fin >> Test_case;

    for (int i=0; i< Test_case ; i++){
        fin >> num;
        vector<int> list;
        memset(cache,-1,sizeof(cache));
        memset(sequence,-1,sizeof(sequence));
        for(int j=0; j< num; j++){
            fin >> sequence[j];
        }

        cout << LIS(-1)-1 << endl;
    }
    return 0;
}