【动态规划】Leetcode 300. 最长递增子序列【中等】

最长递增子序列

• 给你一个整数数组 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 。

解题思路

这个问题可以使用动态规划来解决。我们定义一个长度为 nums.length 的整型数组 dp，

• 其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
• 动态规划的状态转移方程为：
• dp[i] = max(dp[j] + 1) ，其中 0 <= j < i 且 nums[j] < nums[i]
  这个方程的意思是，对于每个元素 nums[i]，我们遍历所有比它小的元素 nums[j]， 如果存在 nums[j] < nums[i]，则以 nums[j] 结尾的最长递增子序列的长度加一就是以 nums[i] 结尾的最长递增子序列的长度。

Java实现

public class LongestIncreasingSubsequence {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxLen = 1;

        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                //前面到的j递增子序列长度 +1
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        return maxLen;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Length of LIS: " + lis.lengthOfLIS(nums)); // Output: 4 (the LIS is [2, 3, 7, 101])
    }
}

时间空间复杂度

• 时间复杂度：外层循环遍历了数组nums，内层循环遍历了0到i - 1，时间复杂度为O(n^2)，其中n为数组nums的长度。

• 空间复杂度：使用了长度为n的数组dp，空间复杂度为O(n)。