算法：最长递增子序列解法记录

题目

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

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

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]输出：1

题目分析

给定一个整数数组 nums，要求找到其中最长的严格递增子序列的长度。严格递增意味着每个数都比前一个数大，也就是说序列中的每个元素都要比其前面的元素大。

举个例子，假设 nums = [10, 9, 2, 5, 3, 7, 101, 18]，其中的最长严格递增子序列为 [2, 3, 7, 101]，所以结果就是 4，也就是该子序列的长度。

思路

• 子序列的定义：子序列是数组中任意几个元素的顺序组合，可以不连续。比如，在 [3, 6, 2, 7] 中，[3, 2, 7] 或者 [6, 7] 都是子序列。

• 递增的定义：严格递增的子序列要求每一个数字都比前一个大，所以如果一个子序列是 [x1, x2, ..., xn]，那么必须满足 x1 < x2 < ... < xn。

• 动态规划的思路：我们可以使用动态规划来解决这个问题。我们定义一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。初始时，每个位置的子序列长度至少为 1，因为每个元素本身就是一个递增子序列。

• 递推公式：对于每一个元素 nums[i]，我们会检查它之前的所有元素 nums[j]，如果 nums[i] 大于 nums[j]，那么 nums[i] 可以延续以 nums[j] 结尾的递增子序列。因此，更新 dp[i] 为 dp[i] = max(dp[i], dp[j] + 1)，表示如果以 nums[j] 结尾的子序列可以扩展到 nums[i]，则更新 dp[i] 的值。

• 最终结果：最长递增子序列的长度就是 dp 数组中的最大值。

详细解读

• dp[i] 的定义：

  • dp[i] 表示以 nums[i] 这个元素为结尾的最长递增子序列的长度。

  • 你可以想象一下，每次考虑到 nums[i] 时，你要确定之前所有比 nums[i] 小的元素 nums[j]（j < i），并且看看是否可以把 nums[i] 加到这些子序列的末尾，来形成一个新的递增子序列。

  • 每一个位置的初始值是 1，因为至少 nums[i] 本身就是一个递增子序列（长度为 1）。

• 如何更新 dp[i]：

  • 我们会从每个元素 nums[i] 向前检查所有前面的元素 nums[j]（j < i）。如果 nums[i] 比 nums[j] 大，说明 nums[i] 可以接在 nums[j] 的递增子序列后面，形成一个新的递增子序列。

  • 所以，我们尝试更新 dp[i] 的值dp[i] = Math.max(dp[i], dp[j] + 1);

    这个式子的意思是：如果 nums[i] 大于 nums[j]，则可以在 dp[j] 的基础上延伸一个新的元素 nums[i]，所以 dp[i] 可能会变大。

    • dp[j] + 1：表示以 nums[j] 结尾的最长递增子序列长度，再加上当前的 nums[i]。

    • Math.max(dp[i], dp[j] + 1)：更新 dp[i]，即保留之前的值和新的 dp[j] + 1 之间的较大值。

• 如何求解最终的结果：

  • 最终，我们需要得到 整个数组中最长递增子序列的长度。而这个长度其实就是 dp 数组中的最大值，表示所有以不同元素结尾的最长递增子序列的最大长度。

  • 所以，我们用以下方式得到最终结果：

    maxLength = Math.max(maxLength, dp[i]);

    这会遍历 dp 数组，得到其中的最大值。

举例分析 

假设有一个数组 nums = [10, 9, 2, 5, 3, 7, 101, 18]，我们来看如何通过动态规划得到最长递增子序列的长度。

1. 初始化 dp 数组为：

   dp = [1, 1, 1, 1, 1, 1, 1, 1]

   因为每个元素初始时自己的递增子序列长度为 1。

2. 遍历 nums 数组，更新 dp 数组：

   • i = 1, nums[i] = 9，检查所有 j < 1 的元素。没有比 9 小的元素，所以 dp[1] 还是 1。

   • i = 2, nums[i] = 2，检查所有 j < 2 的元素。没有比 2 小的元素，所以 dp[2] 还是 1。

   • i = 3, nums[i] = 5，检查所有 j < 3 的元素：

     • nums[0] = 10，nums[0] > nums[3]，不更新。

     • nums[1] = 9，nums[1] > nums[3]，不更新。

     • nums[2] = 2，nums[2] < nums[3]，更新 dp[3] = dp[2] + 1 = 2。

   • i = 4, nums[i] = 3，检查所有 j < 4 的元素：

     • nums[0] = 10，nums[0] > nums[4]，不更新。

     • nums[1] = 9，nums[1] > nums[4]，不更新。

     • nums[2] = 2，nums[2] < nums[4]，更新 dp[4] = dp[2] + 1 = 2。

     • nums[3] = 5，nums[3] > nums[4]，不更新。

   • i = 5, nums[i] = 7，检查所有 j < 5 的元素：

     • nums[0] = 10，nums[0] > nums[5]，不更新。

     • nums[1] = 9，nums[1] > nums[5]，不更新。

     • nums[2] = 2，nums[2] < nums[5]，更新 dp[5] = dp[2] + 1 = 2。

     • nums[3] = 5，nums[3] < nums[5]，更新 dp[5] = Math.max(dp[5], dp[3] + 1) = 3。

     • nums[4] = 3，nums[4] < nums[5]，更新 dp[5] = Math.max(dp[5], dp[4] + 1) = 3。

   • 继续这个过程直到遍历完整个数组，最终得到

     dp = [1, 1, 1, 2, 2, 3, 4, 4]

3. 最终结果：最大的 dp[i] 是 4，因此最长递增子序列的长度是 4。

代码 

public class Solution { public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) { return 0; // 如果输入数组为空或没有元素，返回0 } // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度 int n = nums.length; int[] dp = new int[n]; // 初始时，每个元素的子序列长度为1 for (int i = 0; i < n; i++) { dp[i] = 1; } // 遍历每个元素，检查它之前的所有元素 for (int i = 1; i < n; i++) { for (int j = 0; j  nums[j]) {  dp[i] = Math.max(dp[i], dp[j] + 1); // 更新 dp[i] 的值 } } } // 找到 dp 数组中的最大值，表示最长递增子序列的长度 int maxLength = 0; for (int i = 0; i < n; i++) { maxLength = Math.max(maxLength, dp[i]); } return maxLength; } public static void main(String[] args) { Solution solution = new Solution(); int[] nums = {10, 9, 2, 5, 3, 7, 101, 18}; System.out.println(\"Longest Increasing Subsequence Length: \" + solution.lengthOfLIS(nums)); }}