종만북 LIS C++ 풀이 (코드제공)

1. 문제 설정 확인

또 다른 DP의 클래식 문제인, LIS (Longest Incresaing Subsequence) 문제이다.

3. 해답 코드

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int cache[1001];
int size;
vector<int> field;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(cache, 0, sizeof(cache));
    cin >> size;
    for(int i = 0; i < size; i++){
        int tmp;
        cin >> tmp;
        field.push_back(tmp);
    }
    int MaxLength = 0;
    for(int i = 1; i < size; i++){
        cache[i] = 1;
        for(int j = i - 1; j >= 0; j--){
            if(field[i] > field[j])
                cache[i] = cache[j] + 1;
        }
        if(cache[i] > MaxLength) {
            MaxLength = cache[i];
        }
    }
    cout << MaxLength;
}

Source

• 종만북, 2022.07.22
• CLion