일단 알고리즘 문제해결전략 책을 보면서 공부하는 학생입니다.
LIS 문제를 보고 풀면서 책에 있는 코드를 따라 쳐서 정답인지 검증하기위해 알고스팟에 답안 제출을 했습니다. 결과는 오답으로 나오더군요.
예시를 그대로 입력해서 확인해보았지만 문제는 없었습니다.
제가 혹시 모르는 부분에서 문제가 있는지 궁금해서 글 남깁니다.

#include <iostream>
#include <vector>

using namespace std;

int n;
int cache[500], S[500];

int lis3(int);

int main()
{
    int times = 0;
    cin >> times;
    vector<int> answer;

    for(int i = 0; i < times; ++i)
    {
        cin >> n;
        for(int j = 0; j < n; ++j)
            cin >> S[j];
        for(int j = 0; j < 500; ++j) cache[j] = -1;
        answer.push_back(lis3(-1)-1);
    }

    for(int i = 0; i <times; ++i) cout << answer[i] << endl;
    return 0;
}

int lis3(int start)
{
    int& ret = cache[start+1];
    if(ret != -1) return ret;
    ret = 1;
    for(int next = start + 1; next < n; ++next)
        if(start == -1 || S[start] < S[next])
            ret = max(ret, lis3(next) +1);
    return ret;
}