DP #5 : Russian Doll Envelopes

DP #5: Russian Doll Envelopes

Problem Statement: here

Solution:

This is a follow-up question from DP #4: Box stacking problem. This is slightly easy variant but involves a similar concept. I am not going to explain the DP solution which takes O(n^2) time. 

The implementation is easy and straightforward as in Box stacking Problem.

Code: 

class Solution { public: int maxEnvelopes(vector<vector<int>>& a) { sort(begin(a), end(a), greater<vector<int>>()); int dp[a.size()+5]; int mx = 0; for(int i=0;i<a.size();i++){ dp[i+1] = 1; for(int j=0;j<i;j++){ if (a[j][0] > a[i][0] and a[j][1] > a[i][1]){ dp[i+1] = max(dp[i+1],dp[j+1]+1); } } mx = max(mx,dp[i+1]); } return mx; }

};

What next -?

Try out the O(NlogN) version of above code. We are simply doing the LIS and

that can be done in O(NLogN).