가장 긴 증가하는 부분 수열(LIS)

https://algospot.com/judge/problem/read/LIS#c16488

굉장히 정형화된 알고리즘이라서, 이외의 구현은 틀렸다고 봐도 된다.

참고로 BOJ에 이와 관련된 문제들이 많다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int main(void)
{
    int T = 0, N = 0, num = 0;
 
    scanf("%d", &T);
 
    while (T--)
    {
        int result = -1;
 
        vector<int> v;
 
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++)
        {
            scanf("%d", &num);
 
            v.push_back(num);
        }
 
        int dp[600] = { 0, };
 
        for (int i = 0; i < N; i++)
        {
            dp[i] = 1;
 
            for (int j = 0; j < i; j++)
            {
                if (v.at(i) > v.at(j) && dp[j] + 1 > dp[i])
                {
                    dp[i] = dp[j] + 1;
                }
            }
 
            result = max(result, dp[i]);
        }
 
        printf("%d\n", result);
    }
 
    return 0;
}