Untitled

unknown
plain_text
a month ago
1.2 kB
0
Indexable
Never
```class Solution {
public:
bool check(int curr,int prev,vector<vector<int>>&cuboids){
if(cuboids[curr][0]>=cuboids[prev][0] &&cuboids[curr][1]>=cuboids[prev][1] && cuboids[curr][2]>=cuboids[prev][2]) return true;
return false;
}

int lis(vector<vector<int>>&cuboids,int curr,int prev,vector<vector<int>>&dp){
int n=cuboids.size();
if(curr==n) return 0;

if(dp[curr][prev+1]!=-1) return dp[curr][prev+1];

int include=0;
if(prev==-1 || check(curr,prev,cuboids)){
include= cuboids[curr][2]+ lis(cuboids,curr+1,curr,dp);
}
int exclude=lis(cuboids,curr+1,prev,dp);
return dp[curr][prev+1]=max(include,exclude);

}
int maxHeight(vector<vector<int>>& cuboids) {
//sort each row to get height at index2
for(auto &a:cuboids) sort(a.begin(),a.end());
//sort entire columns
sort(cuboids.begin(),cuboids.end()); //sort based on earlier index, highe rindex to break tie
//do lis on height
int n=cuboids.size();
vector<vector<int>> dp(n,vector<int>(n+1,-1));
return lis(cuboids,0,-1,dp);

}
};```