# Based on Longest Increasing Sequence: Java, DFS, O(n^2)

• ``````public class Solution
{
int[] tempArr;
int maxLen;
public int maxEnvelopes(int[][] envelopes)
{
Arrays.sort(envelopes, new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2)
{
return o1[0] - o2[0];
}
});
maxLen = Integer.MIN_VALUE;
tempArr = new int[envelopes.length];
for(int i = 0; i < envelopes.length; i++)
tempArr[i] = -1;
for(int i = envelopes.length - 1; i >= 0 ; i--)
maxLen = Math.max(lis(i, envelopes), maxLen);
return maxLen == Integer.MIN_VALUE? 0 : maxLen;
}
int lis(int i, int[][] envelopes)
{
if(tempArr[i] != -1)
return tempArr[i];
int tempArrVal = Integer.MIN_VALUE, maxVal = tempArrVal;
for(int j = i + 1; j < envelopes.length; j++)
{
if(envelopes[i][1] < envelopes[j][1] && envelopes[i][0] < envelopes[j][0])
tempArrVal = lis(j, envelopes);
maxVal = Math.max(maxVal, tempArrVal);
}
tempArr[i] = 1 + (maxVal == Integer.MIN_VALUE? 0: maxVal);
return tempArr[i];
}
}``````

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