백준 10835번 C++

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int MAX = 2001;
int n;
int leftnum[MAX], rightnum[MAX];
int cache[MAX][MAX];

int maxscore(int lindex, int rindex) {
	if (lindex >= n || rindex >= n)
		return 0;
	int &answer = cache[lindex][rindex];

	if (answer != -1)
		return answer;

	answer = 0;
	if (leftnum[lindex] > rightnum[rindex])
		answer = maxscore(lindex, rindex + 1) + rightnum[rindex];
	answer = max(answer, maxscore(lindex + 1, rindex));
	answer = max(answer, maxscore(lindex + 1, rindex + 1));
	return answer;
}

int main(void) {
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> leftnum[i];
	for (int i = 0; i < n; i++)
		cin >> rightnum[i];

	memset(cache, -1, sizeof(cache));
	cout << maxscore(0, 0) << endl;
	return 0;
}