Wrong output in "Optimal game strategy-II" problem

#1

THIS IS CODE HAS PASSED 11 TEST CASES BUT FAILED ONLY IN LAST ONE. PLEASE CORRECT ME.

import java.util.*;
public class Main
{
static long[] arr;
public static long optimalGame(int i, int j,long[][] dp)
{
if (i > j)
return 0;
if(dp[i][j]!=-1)
return dp[i][j];
long pickFirst = arr[i] + Math.min(optimalGame(i + 2, j,dp), optimalGame(i + 1, j - 1,dp));
long pickLast = arr[j] + Math.min(optimalGame(i, j - 2,dp), optimalGame(i + 1, j - 1,dp));
long ans = Math.max(pickFirst, pickLast);
dp[i][j]=ans;
return ans;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
arr = new long[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextLong();
long dp[][]=new long[n+1][n+1];
for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
dp[j][k]=-1;
System.out.println(optimalGame(0, n - 1,dp));

}

}

#2

@vinay86048,
don’t pass dp as an argument in the OptimalGame method. Keep it global.

for(int j=0;j<n;j++)
for(int k=0;k<n;k++)
It should be j<=n and k<=n

#3

Still same problem. Last case is not passing.

import java.util.*;
public class Main
{
static long dp[][];
static long[] arr;
public static long optimalGame(int i, int j)
{
if (i > j)
return 0;
if(dp[i][j]!=-1)
return dp[i][j];
long pickFirst = arr[i] + Math.min(optimalGame(i + 2, j), optimalGame(i + 1, j - 1));
long pickLast = arr[j] + Math.min(optimalGame(i, j - 2), optimalGame(i + 1, j - 1));
long ans = Math.max(pickFirst, pickLast);
dp[i][j]=ans;
return ans;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
arr = new long[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextLong();
dp=new long[n+1][n+1];
for(int j=0;j<=n;j++)
for(int k=0;k<=n;k++)
dp[j][k]=-1;
System.out.println(optimalGame(0, n - 1));

}

}

#4

@vinay86048,
your code is correct. I have checked all the test cases. Please write a mail to [email protected] regarding your problem. Might be a server issue. Your code is absolutely correct now.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.