vlambda博客
学习文章列表

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

我们用dp[i]表示数组的前i个元素构成的最长上升子序列，如果要求dp[i]，我们需要用num[i]和前面的数字一个个比较，如果比前面的任何一个数字大，说明加入到他的后面可以构成一个上升子序列 ，就更新dp[i]。我们就以[8，2，3，1，4]为例来画个图看一下

我们再来看下代码

 1public int lengthOfLIS(int[] nums) {
 2    //边界条件判断
 3    if (nums == null || nums.length == 0) {
 4        return 0;
 5    }
 6    int[] dp = new int[nums.length];
 7    //初始化数组dp的每个值为1
 8    Arrays.fill(dp, 1);
 9    int max = 1;
10    for (int i = 1; i < nums.length; i++) {
11        for (int j = 0; j < i; j++) {
12            //如果当前值nums[i]大于nums[j]，说明nums[i]可以和
13            //nums[j]结尾的上升序列构成一个新的上升子序列
14            if (nums[i] > nums[j]) {
15                dp[i] = Math.max(dp[i], dp[j] + 1);
16                //记录构成的最大值
17                max = Math.max(max, dp[i]);
18            }
19        }
20    }
21    return max;
22}

这题还有一种解决方式就是把找到的上升子序列放到一个集合list中，我们每次遍历的时候都会拿当前值nums[i]和list的最后一个元素比较

1，如果nums[i]比list最后一个元素大，说明nums[i]加入到list的末尾可以构成一个更长的上升子序列，我们就把nums[i]加入到list的末尾。

 1public int lengthOfLIS(int[] nums) {
 2    //list中保存的是构成的上升子序列
 3    ArrayList<Integer> list = new ArrayList<>(nums.length);
 4    for (int num : nums) {
 5        //如果list为空，我们直接把num加进去。如果list的最后一个元素小于num，
 6        //说明num加入到list的末尾可以构成一个更长的上升子序列，我们就把num
 7        //加入到list的末尾
 8        if (list.size() == 0 || list.get(list.size() - 1) < num)
 9            list.add(num);
10        else {
11            //如果num不小于list的最后一个元素，我们就用num把list中第一
12            //个大于他的值给替换掉,这样我们才能保证list中的元素在长度不变
13            //的情况下，元素值尽可能的小
14            int i = Collections.binarySearch(list, num);
15            //因为list是从小到大排序的，所以上面使用的是二分法查找。当i大
16            //于0的时候，说明出现了重复的，我们直接把他替换即可，如果i小于
17            //0，我们对i取反，他就是list中第一个大于num值的位置，我们把它
18            //替换即可
19            list.set((i < 0) ? -i - 1 : i, num);
20        }
21    }
22    return list.size();
23}

这题也是比较常见的一道题，动态规划应该说是最好理解的。如果完全搞懂的话，下面的那种解法其实也是比较经典的。