class Solution {
public int maxEnvelopes(int[][] envelopes) {
//sort the array by the width in ascending order, convert the probelm to LIS
Arrays.sort(envelopes, (a, b)->a[0]-b[0]);
// j in the range of [0, i-1];
// dp[i] = max(1+dp[j],1);
int len = envelopes.length;
int[] memo = new int[len];
int ans = 0;
for(int i=0; i<len; i++){
//min of memo[i] is 1;
memo[i]=1;
for(int j=0; j<i; j++){
if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){
memo[i]=Math.max(memo[i], 1+memo[j]);
}
}
ans = Math.max(ans, memo[i]);
}
return ans;
}
}