[algospot][JLIS] 합친 LIS

문제 : https://www.algospot.com/judge/problem/read/JLIS

---

배열 A, B의 인덱스(indA, indB)를 파라미터로 받는 재귀함수를 만든다.

A[indA], B[indB] 는 증가 부분 수열에 반드시 포함된다고 가정한다.

따라서 A[indA], B[indB]의 최대 값보다 큰 배열 요소만이 증가 부분 수열에 추가 될 수 있다.

int solve(indA, indB){
    int maxNum = max(A[indA], B[indB]);
    for(nextInd = [indA + 1, N)){
        if(maxNum < A[nextInd]) 
            ans = max(ans, solve(nextInd, indB) + 1);
    }
}

위 코드는 배열 A에 정답 배열에 들어갈 수 있는 다음 배열 요소를 찾는 코드이다.

maxNum보다 큰 배열 A의 요소 값을 찾으면 재귀함수를 다시 돌리고 반환된 값에 +1을 더해준다. (+1 = A[indA])

이를 배열 B에도 똑같이 적용한 뒤 구한 최대 길이가 정답이 되고 이를 반환한다.

 

시간복잡도는 O(NM(N+M)).

N, M 범위가 [1,100]이므로 시간내에 가능하다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/algospot/JLIS.cpp

---

#include<limits.h>

LLONG_MIN

long long int 최대값

참고 : <climits> (limits.h)