记录---信封嵌套问题（动态规划）

import java.util.Arrays;
import java.util.Comparator;

public class DP9 {
   
    public static void main(String[] args) {
   
        int[][] test={
   {
   1,2},{
   3,3},{
   2,6},{
   5,5}};
        
        DP9 dp9 = new DP9();
        int res = dp9.maxEnvelopes(test);
        System.out.println(res);
        
    }
    int maxEnvelopes(int[][] envelopes){
   
        int n=envelopes.length;
        //对envelopes二维数组先按宽度从小到大排序，宽度相等按高度降序排序
        Arrays.sort(envelopes, new Comparator<int[]>() {
   
            @Override
            public int compare(int[] o1, int[] o2) {
   
                return o1[0]==o2[0]?o2[1]-o1[1]:o1[0]-o2[0];
            }
        });
        //得到一个高度的数组，实际上就是对高度数组求最长递增子序列长度
        int[] height= new int[n];
        for (int i = 0; i < n; i++) {
   
            height[i]=envelopes[i][1];
        }
        //求最长递增子序列长度
        int res=lengthOfLIS(height);
        return res;
    }
    /* * 求数组的最长递增子序列长度 * */
    int lengthOfLIS(int[] nums){
   
        int n=nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        //计算出dp数组，dp[i]表示到nums[i]这个数字的最长子序列长度
        for (int i = 0; i < n ; i++) {
   
            for (int j = 0; j <i ; j++) {
   
                //找到前面那些结尾比nums[i]小的子序列，把nums[i]接到最后，新的子序列长度加一
                //有可能形成很多种新的子序列，我们选择最长的那一种，保存子序列最长的结果到dp[i]
                if (nums[j]<nums[i]){
   
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        //求在dp数组中的最大值
// Arrays.sort(dp);
// int res = dp[n-1];

        int res=0;
        for (int i = 0; i < n; i++) {
   
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}