Submission #1945963

---

Source Code Expand

#include <iostream>
using namespace std;

typedef long long ll;

int N;
ll A[4010];
ll dp[4010][4010];

ll rec(int l,int r)
{
	if(l > r) return 0;
	if(l == r) return A[l];

	if(dp[l][r] != -1) return dp[l][r];

	ll res = 0;
	ll eat_l = A[l],eat_r = A[r];

	if(A[l + 1] > A[r]) eat_l += rec(l + 2,r);
	else eat_l += rec(l + 1,r - 1);

	if(A[l] > A[r - 1]) eat_r += rec(l + 1,r - 1);
	else eat_r += rec(l,r - 2);

	res = max(eat_l,eat_r);

	return (dp[l][r] = res);
}


int main()
{
	for(int i = 0;i < 4010;i++)
	{
		for(int j = 0;j < 4010;j++)
		{
			dp[i][j] = -1;
		}
	}

	cin >> N;

	for(int i = 0;i < N;i++)
	{
		cin >> A[i];
		A[i + N] = A[i];
	}
	ll result = -1;
	for(int i = 0;i < N;i++)
	{
		result = max(result,rec(i,i + N - 1));
	}

	cout << result << endl;
	return 0;
}

Submission Info

Judge Result