1 2 3 4 5 6 7 8 9 10 11 12 13 14
| #include <bits/stdc++.h>
int dp[505][505]; int helper(vector<int>& A, int l, int r) { if(dp[l][r] != -1) return dp[l][r]; if(l == r) return dp[l][r] = A[l]; return dp[l][r] = max(A[l] - helper(A,l+1,r), A[r] - helper(A,l,r-1)); } int Solution::maxcoin(vector<int> &A) { memset(dp,-1,sizeof dp); int gap = helper(A,0,A.size() - 1), sum = accumulate(begin(A), end(A), 0); return (sum - gap) / 2 + gap; }
|