➤ Problem Link : CODEM4
👉 Hint : Take max and min while computing for dumb and smart player2 respectively
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int arr[32];
int n;
int GameDumb(int i,int j)
{
if(i<1 || j<1 || i>j || i>n || j>n)
return 0;
int ans=arr[i]+max(GameDumb(i+2,j),GameDumb(i+1,j-1)); //left
ans=max(ans,arr[j]+max(GameDumb(i,j-2),GameDumb(i+1,j-1))); //right
return ans;
}
int GameSmart(int i,int j)
{
if(i<1 || j<1 || i>j || i>n || j>n)
return 0;
int ans=arr[i]+min(GameSmart(i+2,j),GameSmart(i+1,j-1)); //left
ans=max(ans,arr[j]+min(GameSmart(i,j-2),GameSmart(i+1,j-1))); //right
return ans;
}
int main()
{
int t;
cin>>t;
string l,s;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>arr[i];
cout<<GameDumb(1,n)<<" ";
cout<<GameSmart(1,n)<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.