backward DP solution in Java


  • 0
    S

    records[i] records the maximum chain can be found from the sorted pairs ( I i+1, .... n-1)
    records[i -1 ] search from i to n - 1 to find the index j which pairs[j][0] > pairs[i-1][1]. records[I-1]'s value is the max of records[I] and 1 + records[j].

    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
        int[] records = new int[pairs.length];
        records[pairs.length - 1] = 1;
        for (int i = pairs.length - 2; i >= 0; i--) {
            int j = i + 1;            
            int curMax = records[j];
            while (j < pairs.length && pairs[j][0] <= pairs[i][1]) {     
                j++;
            }
            
            if (j != pairs.length && 1+ records[j] > curMax) {
                    curMax = 1 + records[j];
            }
    
            records[i] = curMax;
        }
        
        return records[0];
    }

Log in to reply
 

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