알고스팟(algospot) JLIS

실수한 점:

1. 먼저 범위가 정수범위인 것을 확인하지 못했다.

2. 정수 범위기때문에 최솟값 설정시 long long 으로 해야하는것을 알아차리지 못했다.

3. 초기 -1을 넘겨주고 -1일 경우는 그냥 다음 배열로 넘어가도록 하였는데, 예외인 케이스가 존재했다.

 456789, 1234 배열에서 첫번째 배열이 하나라도 진행되었다면(start1 >= 0)  start2는 -1에서 멈춰있어야 하는데, 나는 진입해버렸다. 때문에 오답이 나왔다.

  

#include <iostream>
#include <cstring>
#include <cstdio>
#include <limits>
using namespace std;
const long long NEGINF = numeric_limits<long long>::min();
int arr1[101], arr2[101];
int cache[101][101];
int T;
int N, M;
int jlis(int start1, int start2){
    int& ret = cache[start1 + 1][start2 + 1];
    if(ret != -1) return ret;
    ret = 2;
    long long a = start1 == -1 ? NEGINF : arr1[start1];
    long long b = start2 == -1 ? NEGINF : arr2[start2];
    long long maxNum = max(a, b);
    for(int next = start1 + 1; next < N; ++next){
        if(maxNum < arr1[next]){
            ret = max(ret, jlis(next, start2) + 1);
        }
    }
    for(int next = start2 + 1; next < M; ++next){
        if(maxNum < arr2[next]){
            ret = max(ret, jlis(start1, next) + 1);
        }
    }
    return ret;
}
int main() {
    scanf("%d", &T);
    while(T--){
        memset(cache, -1, sizeof(cache));
        scanf("%d %d", &N, &M);
        for(int i = 0 ; i < N; ++i){
            scanf("%d", arr1 + i);
        }
        for(int i = 0; i < M; ++i){
            scanf("%d", arr2 + i);
        }
        printf("%d\n", jlis(-1, -1) - 2);
    }
    return 0;
}