public int maxEnvelopes(int[][] envelopes) {
if ( envelopes == null
 envelopes.length == 0
 envelopes[0] == null
 envelopes[0].length == 0){
return 0;
}
Arrays.sort(envelopes, new Comparator<int[]>(){
@Override
public int compare(int[] e1, int[] e2){
return Integer.compare(e1[0], e2[0]);
}
});
int n = envelopes.length;
int[] dp = new int[n];
int ret = 0;
for (int i = 0; i < n; i++){
dp[i] = 1;
for (int j = 0; j < i; j++){
if ( envelopes[i][0] > envelopes[j][0]
&& envelopes[i][1] > envelopes[j][1]){
dp[i] = Math.max(dp[i], 1 + dp[j]);
}
}
ret = Math.max(ret, dp[i]);
}
return ret;
}
Simple DP solution


@dasahcc
You should use something like this:
'''
Arrays.sort(a, new Comparator<int[]>() {
public int compare(int a1[], int a2[]) {
return a1[0] * a1[1]  a2[0] * a2[1];
}
});
'''


I got the same thing, perhaps a little more verbose but I find it readable. BTW, this is an easier version of the boxstacking problem:
public int maxEnvelopes(int[][] envelopes) { if (envelopes == null) return 0; if (envelopes.length <= 1) return envelopes.length; int max = 1, n = envelopes.length; Arrays.sort(envelopes, (x, y) > Integer.compare(y[0]*y[1], x[0]*x[1])); // sort by area int[] dp = new int[n]; for(int i = 0; i < n; i++) { dp[i] = 1; int[] inner = envelopes[i]; for(int j = 0; j < i; j++) { int[] outer = envelopes[j]; if (outer[0] > inner[0] && outer[1] > inner[1]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } max = Math.max(max, dp[i]); } return max; }