ALGOSPOT LIS 알고스팟 최대 증가 부분 수열

ALGOSPOT LIS 알고스팟 최대 증가 부분 수열

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cassert>
#include<cstring>
using namespace std;
 
int n;
int cache[501], S[501],C[501];
int idx;
 
//메모제이션을 적용하기 까다로운 최대증가 부분 수열 문제를 
//해결하는 완전 탐색 알고리즘 
int lis(const vector<int> &A) {
    if (A.empty()) return 0;
    int ret = 0;
    for (int i = 0; i < A.size(); i++) {
        vector<int> B;
        for (int j = i + 1; j < A.size(); j++)
            if (A[i] < A[j])
                B.push_back(A[j]);
        ret = max(ret, 1 + lis(B));
    }
    return ret;
}
 
//S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.
int lis2(int start) {
    int&ret = cache[start];
    if (ret != -1) return ret;
    //항상 S[start]는 있기 때문에 길이는 최하 1
    ret = 1;
    for (int next = start + 1; next < n; next++)
        if (S[start] < S[next])
            ret = max(ret, 1 + lis2(next));
    return ret;
}
//lis2함수에서 main에서 for문을 적용시키기 귀찮을 때
int lis3(int start) {
    int &ret = cache[start + 1];
    if (ret != -1) return ret;
    //항상 S[start]는 있기 때문에 길이는 최하 1
    ret = 1;
    for (int next = start + 1; next < n; next++)
        if (start == -1 || S[start] < S[next])
            ret = max(ret, 1 + lis3(next));
    return ret;
}
void lis4(int num)
{
    if (idx == 0 || (idx > 0 && C[idx - 1] <= num)) //해당 숫자가 더 크거나 벡터가 비어있다면
    {
        C[idx++] = num;
        return;
    }
    //증가 부분 순열에 성립하지 않은 숫자라면 삽입할 위치를 찾는다
    int front = 0;
    int rear = idx - 1;
    while (front <= rear) //이진탐색
    {
        int mid = (front + rear) / 2;
        if (C[mid] < num)
            front = mid + 1;
        else
            rear = mid - 1;
    }
    C[rear + 1] = num;
}
 
int main(){
    int cases;
    cin >> cases;
    while (cases--) {
        cin >> n;
        vector<int> A;
        for (int i = 0; i < n; i++) {
            cin >> S[i];
            A.push_back(S[i]);
        }
        cout << lis(A) << "   LIS1" << endl;
        memset(cache, -1, sizeof(cache));
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            maxLen = max(maxLen, lis2(i));
        }
        cout << maxLen <<"   LIS2" <<endl;
 
        memset(cache, -1, sizeof(cache));
        //가상으로 추가 입력한 값이 있으므로 
        //cache[]의 크기가 1커졌으므로 최종 반환값에서 빼주기
        cout << lis3(-1) - 1 << "   LIS3"<< endl;
        
        memset(C, 0, sizeof(C));
        idx = 0;
        for (int i = 0; i < n; i++) 
            lis4(S[i]);
        cout << idx << "   LIS4" << endl;
        
    }
 
    return 0;
}
 
 

문제 출처:https://algospot.com/judge/problem/read/LIS

lis4 함수 사용 방법은 생각도 못했네요. 신기합니다.