[PS] 백준 11053번 - 가장 긴 증가하는 부분 수열

LIS 알고리즘을 사용하면 간단하게 해결할 수 있다.

#include <iostream>

using namespace std;

int a[1000], length[1000], n;

void dpFunc() {
    int res=0;
    for(int i=0; i<n; i++) {
        length[i]=1;
        for(int j=0; j<i; j++)
            if(a[i]>a[j]) length[i]=max(length[i], length[j]+1);
        if(length[i]>res) res=length[i];
    }
    cout << res;
}

int main(void) {
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    dpFunc();
    return 0;
}