Inspired By LIS, easy to understand


  • 0
    F

    Inspired By LIS, easy to understand....
    Then you can optimize it use BinarySearch

    class Solution {
        public int findLongestChain(int[][] pairs) {
            if (pairs == null || pairs.length == 0) {
                return 0;
            }
            
            Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
            
            int[] dp = new int[pairs.length];
            Arrays.fill(dp, 1);
            
            for (int i = 0; i < pairs.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (pairs[i][0] > pairs[j][1]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }        
                }
            }
            
            int maxLen = 0;
            for (int i = 0; i < dp.length; i++) {
                maxLen = Math.max(maxLen, dp[i]);
            }
            
            return maxLen;
            
        }
    }
    
    

Log in to reply
 

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