Can anyone hep me with this question I can think of LIS but am not able to solve it 
Code implement with LIS
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(n) for(ll i=0;i<n;i++)
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
ll t;
cin>>t;
while(t--){
ll n;cin>>n;
vector<pair<ll,ll>>a(n);
f(n)cin>>a[i].first;
f(n){cin>>a[i].second;}
sort(a.begin(),a.end(),[&](pair<ll,ll>a,pair<ll,ll>b){
if(a.first==b.first)return a.second>b.second;
return a.first<b.first;
});
vector<ll>b;
vector<pair<ll,ll>>lp;
ll ans=1;
lp.push_back({-1,-1});
b.push_back(-1);
for(ll i=0;i<n;i++){
if(lp[lp.size()-1].first==a[i].first)continue;
auto it= lower_bound(b.begin(), b.end(), a[i].second);
if (it == b.end()) {
b.push_back(a[i].second);
lp.push_back(a[i]);
}
else {
lp[it-b.begin()]=a[i];
b[it-b.begin()] = a[i].second;
}
}
cout<<lp.size()-1<<endl;
}
}
you could sort the boxes based on height and then find the LIS of the widths of the boxes since then all the boxes chosen will have height in sorted order as well as width in sorted order
like in the example , sort based on height
h : 6 10 10 12
w : 6 5 10 12
and now you could find the LIS of w in this case it will be 3 -> 6 10 12
I tried it but its giving wrong answer Below is my code if yoy can find any testcase or logic error
im a python user so cpp is a bit difficult for me ;-; , could you send me the question link , i will try solving it after todays contest.
Here is the code in python , i have found the LIS using segment tree.
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int: envelopes = sorted(envelopes,key = lambda x:(x[0],-x[1])) L1 = envelopes class SegmentTree: def __init__(self, data): self.n = len(data) self.tree = [0] * (2 * self.n) self.build(data) def build(self, data): for i in range(self.n): self.tree[self.n + i] = data[i] for i in range(self.n - 1, 0, -1): self.tree[i] = max(self.tree[i * 2], self.tree[i * 2 + 1]) def update(self, pos, value): pos += self.n self.tree[pos] = value while pos > 1: pos //= 2 self.tree[pos] = max(self.tree[2 * pos], self.tree[2 * pos + 1]) def query(self, left, right): left += self.n right += self.n max_val = float('-inf') while left < right: if left % 2: max_val = max(max_val, self.tree[left]) left += 1 if right % 2: right -= 1 max_val = max(max_val, self.tree[right]) left //= 2 right //= 2 return max_val k1 = 0 for i in range(len(L1)): k1 = max(k1,L1[i][1]) L = SegmentTree([0 for i in range(k1+1)]) ans = 0 for i in range(len(L1)): f = L.query(0,L1[i][1]) L.update(L1[i][1],1+f) ans = max(ans,1+f) return ansThis is my solution.
The problem link — link.
It is quite similar to the problem you showed, try submitting your answer here, it will show you what test case your answer failed for.
Russian Doll Envelopes