1 9 2 5 7

부분 수열 : 일부 숫자를 지우고 남은 수열

ex) 1 2 5
ex) 1 9 5 7

1 2 9 이딴식으로 순서 바꾸는거 안됨.

순 증가 부분 수열

1 2 5 이런거

LIS

제일 긴 순 증가 부분 수열의 길이 찾기
1 2 5 7 => 길이 4

#pragma region LIS

int cache_LIS[50];
vector<int> seq;

int LIS(int pos)
{
    // 기저사항

    // 캐시 확인
    int& ret = cache_LIS[pos];
    if (ret != -1)
        return ret;

    // 최소 seq[pos]는 있으니 1부터 시작
    ret = 1;

    // 구하기
    for (int next = pos + 1; next < seq.size(); ++next)
        if (seq[pos] < seq[next])
            ret = max(ret, 1 + LIS(next));

    return ret;
}


int main()
{
    ::memset(cache_LIS, -1, sizeof(cache_LIS));

    seq = { 10, 1, 9, 2, 5, 7 };

    int ret = 0;
    for (int pos = 0; pos < seq.size(); ++pos)
        ret = max(ret, LIS(pos));

    return 0;
}

시작점이 10같은 큰수 일 수 있으니 모든 경우에 대해 시작점 다 돌려준다.