Easy DP Java solution


#1

public class Solution {
class Pair{
int first;
int second;
public Pair(int x, int y)
{
this.first=x;
this.second=y;
}
}
public int maxcoin(int[] arr) {
int n=arr.length;
Pair dp[][] = new Pair[n][n];
int i,j,l;
for(i=0;i<n;i++)
dp[i][i]=new Pair(arr[i],0);
for(l=2;l<=n;l++)
{
for(i=0;i<n-l+1;i++)
{
int max=0;
Pair ans;
j=i+l-1;
if(arr[i]+dp[i+1][j].second>arr[j]+dp[i][j-1].second)
ans=new Pair(arr[i]+dp[i+1][j].second, dp[i+1][j].first);
else
ans=new Pair(arr[j]+dp[i][j-1].second, dp[i][j-1].first);
dp[i][j]=ans;
}
}
return (dp[0][n-1].first);
}
}