➤ Problem Link : BRIDGE
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
struct node{
ll x,y;
};
typedef struct node NODE;
NODE arr1[1002];
ll arr2[1002];
ll dp[1002];
bool comp(NODE a,NODE b)
{
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
ll LIS(ll arr[],ll n)
{
ll i,j,ans=dp[0];
for(i=1;i<n;i++)
{
for(j=i-1;j>=0;j--)
if(arr[j]<=arr[i])
dp[i]=max(dp[i],dp[j]+1);
ans=max(ans,dp[i]);
}
return ans;
}
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
for(ll i=0;i<n;i++)
dp[i]=1;
for(ll i=0;i<n;i++)
{
cin>>arr1[i].x;
}
for(ll i=0;i<n;i++)
{
cin>>arr1[i].y;
}
sort(arr1,arr1+n,comp);
for(ll i=0;i<n;i++)
{
arr2[i]=arr1[i].y;
}
cout<<LIS(arr2,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.