➤ Problem Link : BAT2
👉 Hint : Think about 3D DP
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int arr[102];
int dp[101][101][101];
int Batman(int i,int l,int d)
{
if(i==0)
return 0;
int x=INT_MIN;
int y=INT_MIN;
int z=INT_MIN;
if(arr[i]<arr[l])
{
if(dp[i-1][i][d]==-1)
dp[i-1][i][d]=Batman(i-1,i,d);
x=dp[i-1][i][d];
}
if(arr[i]>arr[d])
{
if(dp[i-1][l][i]==-1)
dp[i-1][l][i]=Batman(i-1,l,i);
y=dp[i-1][l][i];
}
if(dp[i-1][l][d]==-1)
dp[i-1][l][d]=Batman(i-1,l,d);
z=dp[i-1][l][d];
return dp[i][l][d]=max(z,max(1+x,1+y));
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++)
cin>>arr[i];
arr[n+1]=INT_MAX;
arr[0]=INT_MIN;
cout<<Batman(n,n+1,0)<<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.