Simple DP Solution, JAVA


  • 1
    J
    class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            
            if(envelopes == null || envelopes.length == 0 || envelopes[0].length == 0) return 0;
            
            Arrays.sort(envelopes, new Comparator<int[]>(){
                @Override
                public int compare(int[] a, int[] b){
                    return a[0] - b[0];
                }
            });
            
            int[] dp = new int[envelopes.length + 1];
            dp[0] = 0;
            int max = 0;
            for(int i = 0; i <= envelopes.length - 1; i ++) {
                dp[i + 1] = 1;
                for(int j = i - 1; j >= 0; j --) {
                    if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
                        dp[i + 1] = Math.max(dp[i + 1], dp[j + 1] + 1);
                    } 
                }
                max = Math.max(dp[i + 1], max);
            }
            
            return max;
        }
    }
    

Log in to reply
 

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