[c언어/c++] JLIS - 합친 LIS 동적계획법

어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다.

두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 합시다. 이 중 가장 긴 수열을 합친 LIS(JLIS, Joined Longest Increasing Subsequence)이라고 부릅시다. 예를 들어 '1 3 4 7 9' 은 '1 9 4' 와 '3 4 7' 의 JLIS입니다. '1 9' 와 '3 4 7' 을 합쳐 '1 3 4 7 9'를 얻을 수 있기 때문이지요.

A 와 B 가 주어질 때, JLIS의 길이를 계산하는 프로그램을 작성하세요.

문제 링크 - https://algospot.com/judge/problem/read/JLIS

#include<stdio.h>
#include<memory.h>
#include<algorithm>
#include<limits.h>
using namespace std;
int n,n2,loop;
int seq[520],seq2[520];
int cache[520][520];
int lis(int,int);
int main(){
 scanf("%d",&loop);
 for(int c = 0 ; c < loop ; c++){
  int ans = 0;
  memset(cache,-1,sizeof(cache));
  scanf(" %d",&n);
  scanf(" %d",&n2);
  for(int i = 0 ; i < n ; i++) scanf(" %d",&seq[i]);
  for(int i = 0 ; i < n2 ; i++) scanf(" %d",&seq2[i]);
  for(int i = -1 ; i < n ; i++){
   for(int j = -1 ;j < n2 ; j++){
    ans = max(ans,lis(i,j));
   }
  }
  printf("%d\n",ans);
 }
 return 0;
}
int lis(int start,int start2){
 if(cache[start+1][start2+1] != -1) return cache[start+1][start2+1];
 cache[start+1][start2+1] = 0;
 long long a = (start == -1) ? LLONG_MIN : seq[start];
 long long b = (start2 == -1) ? LLONG_MIN : seq2[start2];
 long long max0 = max(a,b);
 for(int next = start + 1 ; next < n ; next++)
  if(max0 < seq[next]) 
   cache[start+1][start2+1] = max(cache[start+1][start2+1],lis(next,start2)+1);
 for(int next2 = start2 + 1 ; next2 < n2 ; next2++)
  if(max0 < seq2[next2]) 
   cache[start+1][start2+1] = max(cache[start+1][start2+1],lis(start,next2)+1);
 return cache[start+1][start2+1];

}