leetcode:300 最长递增子序列

铺垫

• 什么是子序列？

子序列，就是按照”父“序列，衍生出的新序列的一种，最大的特点，就是可以不 连续，注意：不连续，在刷题的过程中（特别是滑动窗口的题型），我们经常会遇到 ：子串，子序列的字眼；子串：是从父串中截取一段的产物，其顺序，还是按照父串的顺序来设定的； 如：String a1 = “123456”; String a2 = “456”; a2就是a1 的子串，String a3 = “1356”,a3 可以看作是 a1 的子序列；

正题

• 题目描述：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

• 难度 中等

• 字节跳动面试出现：23 次；

• 测试数组：{10, 9, 2, 5, 3, 7, 101, 18}

解题思路

• 看题目，有个最字，请养成一个思维：是不是 动态规划？

• 动态规划题目的特点：

  • 计数类型：
    • 有多少种方式 do sth
  • 求最大值，最小值：
    • 最长上升子序列长度
  • 求存在性（问：是？ 问：否？）
    • 能不能取出 k 个数，使得和是 sum

• 第一步： 确定状态

   // 状态数组，为了记录数组中，每一个 index 下，有最多有几个递增的子序列；
   int [] dp  = new int [length];
   // 初始化转态,都是 1；
   Arrays.fill(dp,1);
     
复制代码

 ps: 你可能会疑惑，为啥不是 0 ，要是找一个倒序增长的数组，那就是没有（0 个）递增的子序列啊？
 哈哈，有这个疑问是对的，说明你已经动脑思考了，行，请你留意，在原题的示例3 中；输入：nums = [7,7,7,7,7,7,7] 输入：1，所以，最次，也得返回个 1；
复制代码

• 第二步： 状态转移方程
  • 求最值，肯定少不了 Math.max() 或者 Math.min();
  • 假设 {10, 9, 2, 5, 3, 7, 101, 18} 先去取一个范围，假如 取 [ 10，9，2]，我们固定 2，分别10，9 和 2 比较大小，发现，没有递增的；
  • 要保证，固定的值nums[right]，大于与和比较的nums[left]，我们才决定是否将其value放在当前dp[left] 的状态中；

 ps:我说的固定，有点像滑动窗口，有意思的是：在固定一个值以后a 后，我们会取 a左边的所有值，同 a 做 比较，看一下部分比较的流程吧：
复制代码

原数组：[10, 9, 2, 5, 3, 7, 101, 18]
第0次: nums[1]:9, nums[0]:10, 当前 dp 状态：[1, 1, 1, 1, 1, 1, 1, 1]
———————————————————————
第0次: nums[2]:2, nums[0]:10, 当前 dp 状态：[1, 1, 1, 1, 1, 1, 1, 1]
第1次: nums[2]:2, nums[1]:9, 当前 dp 状态：[1, 1, 1, 1, 1, 1, 1, 1]
———————————————————————
第0次: nums[3]:5, nums[0]:10, 当前 dp 状态：[1, 1, 1, 1, 1, 1, 1, 1]
第1次: nums[3]:5, nums[1]:9, 当前 dp 状态：[1, 1, 1, 1, 1, 1, 1, 1]
第2次: nums[3]:5, nums[2]:2, 当前 dp 状态：[1, 1, 1, 2, 1, 1, 1, 1]
———————————————————————
第0次: nums[4]:3, nums[0]:10, 当前 dp 状态：[1, 1, 1, 2, 1, 1, 1, 1]
第1次: nums[4]:3, nums[1]:9, 当前 dp 状态：[1, 1, 1, 2, 1, 1, 1, 1]
第2次: nums[4]:3, nums[2]:2, 当前 dp 状态：[1, 1, 1, 2, 2, 1, 1, 1]
第3次: nums[4]:3, nums[3]:5, 当前 dp 状态：[1, 1, 1, 2, 2, 1, 1, 1]
———————————————————————
第0次: nums[5]:7, nums[0]:10, 当前 dp 状态：[1, 1, 1, 2, 2, 1, 1, 1]
第1次: nums[5]:7, nums[1]:9, 当前 dp 状态：[1, 1, 1, 2, 2, 1, 1, 1]
第2次: nums[5]:7, nums[2]:2, 当前 dp 状态：[1, 1, 1, 2, 2, 2, 1, 1]
第3次: nums[5]:7, nums[3]:5, 当前 dp 状态：[1, 1, 1, 2, 2, 3, 1, 1]
第4次: nums[5]:7, nums[4]:3, 当前 dp 状态：[1, 1, 1, 2, 2, 3, 1, 1]
———————————————————————

• 加粗的部分，就是我们在做比较的时候，固定的值；

代码

  public int lengthOfLIS4(int[] nums) {
        int length = nums.length;
        if (length < 2) {
            return length;
        }
        int[] dp = new int[length];
        Arrays.fill(dp, 1);
        System.out.println(Arrays.toString(nums));
        for (int rightIndex = 1; rightIndex < length; rightIndex++) {
            System.out.println("|---------------------------------------------------------------------|");
            for (int leftIndex = 0; leftIndex < rightIndex; leftIndex++) {
                // 右边的数，大于左边的数，才有可能做 +1 操作
                if (nums[rightIndex] > nums[leftIndex]) {
                    dp[rightIndex] = Math.max(dp[rightIndex], dp[leftIndex] + 1);
                }
                System.out.println("第"+leftIndex+"次: "+"nums[" + rightIndex + "]:" + nums[rightIndex] + ", nums[" + leftIndex + "]:" +nums[leftIndex]+",  当前 dp 状态："+ Arrays.toString(dp));
            }
        }

        // 遍历 dp数组，取最大值
        int res = 0;
        for (int i = 0; i < length; i++) {
            res = Math.max(res, dp[i]);
        }

        return res;
    }

复制代码

我思

• debug 和 log 对于刷算法题，真的很有作用；

• 在使用 2 层 for 循环遍历数组时，who 和 who 做比较，真的很有必要了解清楚…