Using longest increasing subsequence


  • 0
    F
        public int maxEnvelopes(int[][] envelopes) {
            Arrays.sort(envelopes, (o1, o2) -> o1[0] != o2[0] ? Integer.compare(o1[0], o2[0]) : Integer.compare(o2[1], o1[1]));
            int[] dp = new int[envelopes.length];
            int len = 0;
            for (int[] envelope : envelopes) {
                int idx = Arrays.binarySearch(dp, 0, len, envelope[1]);
                if (idx < 0) {
                    idx = -idx - 1;
                }
                dp[idx] = envelope[1];
                if (idx == len) {
                    len++;
                }
            }
            return len;
        }

Log in to reply
 

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