가장 긴 증가하는 부분 수열 : 합친 LIS

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 

#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000009
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N, M;
ll NEGINF = numeric_limits<ll>::min();
int A[10001], B[10001];
int cache[10001][10001];

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < M; i++) cin >> B[i];
}

int jlis(int indexA, int indexB) {
	int& ret = cache[indexA+1][indexB+1];
	if (ret != -1) return ret;

	ret = 2;
	ll a = (indexA == -1 ? NEGINF : A[indexA]);
	ll b = (indexB == -1 ? NEGINF : B[indexB]);
	ll maxElement = max(a, b);

	for (int nextA = indexA + 1; nextA < N; ++nextA) {
		if (maxElement < A[nextA]) {
			ret = max(ret, jlis(nextA, indexB) + 1);
		}
	}

	for (int nextB = indexB + 1; nextB < M; ++nextB) {
		if (maxElement < B[nextB]) {
			ret = max(ret, jlis(indexA, nextB) + 1);
		}
	}

	return ret;
}

int solution() {
	memset(cache, -1, sizeof(cache));
	int answer = 0;
	answer = max(answer, jlis(-1, -1) - 2);
	return answer;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;
	 
	return 0;
}