책에서 쉽다고 한 JLIS 문제를 몇 일간 헤매다가 도움을 구하고 글을 올립니다. 코드를 직접 올리고 조언을 구하는 것이 안된다는 것은 알지만, 문제의 뎃글에 있는 예제와 sample까지 모두 통과했는데도, 검증시 오답이 나오니 원인이 뭔지 찾기가 힘드네요.

그럼 신경써서 글 읽어주셔서 감사합니다.

~~~ c++

#include
#include

#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define NEGINF (-987654321)

int len_a, len_b;
int a[100], b[100];

int cache[101][101];

int get_max_jlis(int idx_a, int idx_b)
{
int *pret;
long long la, lb, max_value;
int next_a, next_b;

// cache
pret = &cache[idx_a+1][idx_b+1];
if (*pret != -1)    return *pret;

*pret = 2;
la = (idx_a == -1 ? NEGINF : a[idx_a]);
lb = (idx_b == -1 ? NEGINF : b[idx_b]);
max_value = MAX(la, lb);

for (next_a = idx_a + 1; next_a < len_a; ++next_a)
    if (max_value < a[next_a])
        *pret = MAX(*pret, get_max_jlis(next_a, idx_b) + 1);

for (next_b = idx_b + 1; next_b < len_b; ++next_b)
    if (max_value < b[next_b])
        *pret = MAX(*pret, get_max_jlis(idx_a, next_b) + 1);
return *pret;

}

int main()
{
int c, i, j;

scanf("%d", &c);
while (c--) {
    scanf("%d %d", &len_a, &len_b);
    for (i = 0; i < len_a; ++i)
        scanf("%d", &a[i]);
    for (i = 0; i < len_b; ++i)
        scanf("%d", &b[i]);

    // Init
    memset(cache, -1, sizeof(cache));

    // Get Value
    printf("%d\n", get_max_jlis(-1, -1)-2);
}
return 0;

}
~~~