Unable to solve optimal game stategy

#1
#2

Your logic is correct, try using long long int as Test cases are very long. If it still passes, you can still ask for it :slight_smile:

#3

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll sum=0;
ll arr[100][100];
ll genrt(ll a[],ll n)
{
memset(arr,-1,sizeof(arr));
for(ll i=0;i<n;i++)
for(ll j=0;j<n;j++)
{
if(i==j)
arr[i][j]=a[i];
if(i>j)
arr[i][j]=0;
}
for(ll i=n-1;i>-1;i–)
{
for(ll j=0;j<n;j++)
{
if(arr[i][j]==-1)
{
ll op1=a[i]+min(arr[i+2][j],arr[i+1][j-1]);
ll op2=a[j]+min(arr[i][j-2],arr[i+1][j-1]);
arr[i][j]=max(op1,op2);
}
}
}
return arr[0][n-1];
}
int main()
{
ll n;
cin>> n;
ll a[n];
for(ll i=0;i<n;i++)
cin>> a[i];
//int arr[n][n];
ll ans=genrt(a,n);
cout<<ans<<endl;
}

#4

i changed it but error still occuring

#5

Please share your code using ide.codingblocks.com as it would be easy to debug it.

#6
#7

test case 2 is not solved yet.

#8

Debugging it, will let you know your mistake.

#9

Hey @sunneykumar309 why your test case is not getting passed is because with an input of
INPUT
12
50 75 52 96 89 33 20 94 95 50 71 3
Expected Output is: 377
Your Output is: 376

#10

ok…

#11

Your logic and implementation is good , no doubt in that , just try it using recursion and without dp, as it would be easy for you to understand how you program is working

#12

ok i will try recursion…

#13

If your doubt is solved, please mark it as resolved :smile:

#14

ll genrt(ll a[],ll n,ll i, ll j)
{
// base case
if (j == i + 1)
return max(a[i], a[j]);
// recursive
ll op1=a[i]+min((a,n,i+2,j),(a,n,i+1,j-1));
ll op2=a[j]+min((a,n,i,j-2),(a,n,i+1,j-1));
return sum+=max(op1,op2);
}

#15

WA …

#16 
if (i>j) return 0; // this should be your base case
int op1 = a[i] + min(f(a, i + 2, j), f(a, i + 1, j - 1));
int op2 = a[j] + min(f(a, i + 1, j - 1), f(a, i, j - 2));
return max(op1, op2);
1 Like
#17

ok thanks…

#18

Marking it as resolved. Don’t forget to give star rating :smile: