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


  • 0
    V
    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];
        }
    }

Log in to reply
 

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