# UP-BOTTOM DP. Why TLE?

• ``````public class Solution {
public int maxEnvelopes(int[][] envelopes) {
HashMap<Integer,HashMap<Integer,Integer>> dp = new HashMap<Integer,HashMap<Integer,Integer>>();
Arrays.sort(envelopes,new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});

int max = 1 ;
for (int i=0; i< envelopes.length;i++) {
max = Math.max(max, maxdp(dp,envelopes,envelopes[i][0],envelopes[i][1],i));
}
return max;
}

private int maxdp(HashMap<Integer,HashMap<Integer,Integer>> dp, int[][] envelopes, int width, int height, int idx) {
if (dp.containsKey(width) && dp.get(width).containsKey(height)) {
return dp.get(width).get(height);
}
int max = 1;
for (int i = 0; i<idx && envelopes[i][0]<width;i++) {
if (envelopes[i][1]<height) {
max = Math.max(max,1+maxdp(dp,envelopes,envelopes[i][0], envelopes[i][1],i));
}
}
HashMap<Integer, Integer> temp = new HashMap<Integer, Integer>();
if (dp.containsKey(width)) {
temp = dp.get(width);
}
temp.put(height,max);
dp.put(width, temp);
return max;
}
``````

I use the DP idea to solve this question. And before it I sort the envelopes. The running time is O(n^2). Why is it TLE?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.