最长上升子序列

- 日理万妓 2022-12-04 07:57 235阅读 0赞

# 最长上升子序列 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/longest-increasing-subsequence/

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/

## 2、题目要求 ##

> 题目描述

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

> **示例:**

输入: [10,9,2,5,3,7,101,18]
    输出: 4 
    解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

> **说明:**

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。  
你算法的时间复杂度应该为 O(n2) 。

> **进阶:**

你能将算法的时间复杂度降低到 O(nlogn) 吗?

## 3、代码思路 ##

人与人的差距咋就这么大呢？我想这道题硬是想了好久。。。

1.  动态规划的难点在于，在还没有开始进行动态规划逻辑的编写时，我们就需要明确 `dp[]` 数组的含义，动态规划的目的是将一个复杂的大问题分解成易于解决的小问题，`dp[]` 数组的作用就是存储子问题的结果，便于后续的大问题求解时，能够直接调用该结果
2.  既然本题中需要求整个数组(`nums`)的最长上升序列，我们定义 `dp[i]` 存储子数组 `nums[0]~nums[i]` 的最长上升子序列长度(一定要算上 `nums[i]`)，当有了 `dp[]` 数组之后，我们需要求 `nums[0]~nums[i]` 的最长上升子序列长度时，只需要 `nums[0]~nums[i]` 和 `dp[0]~dp[i-1]` 就能求出 `dp[i]`，当求出整个数组的 `dp[]` 数组之后，取 `dp[]` 数组中的最大值即是最长上升子序列的长度
3.  如何根据子数组的最长上升子序列下一步的最长上升子序列呢？即如何根据 `nums[0]~nums[i]` 和 `dp[0]~dp[i-1]` 求出 `dp[i]` 呢？我们使用 `for` 循环遍历 `nums[0]~nums[i-1]`(`for (int j = 0; j < i; j++) {`)，然后将每个 `nums[j]` 依次与 `nums[i]` 比较，如果 `nums[j] < nums[i]`，则说明`nums[j]` 后面加上 `nums[i]` 能够组成上升序列，我们记录此时 `dp[j]` 的值，并挑选出其中的最大值加 `1`(加上 `nums[i]` 之后，子序列长度加 `1`)，作为 `dp[i]` 的取值
4.  在遍历过程中，我们可以实时记录当前最长上升子序列的值，这样就不用等到遍历结束之后，再去遍历 `dp[]` 数组中寻找最大的值

--------------------

啥也不说了，对于整个动态规划的答题流程，直接来看张图(图来自 `LeetCode` 官方图解)

![image-20200906125916097][]

## 4、代码实现 ##

代码

static class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
            // Guard Safe
            if (nums.length == 0) {
        
                return 0;
            }
    
            int[] dp = new int[nums.length];
            // 数组第 0 个元素的最长上升子序列就是他本身，所以 dp[0] = 1
            dp[0] = 1;
            // maxLength 用于记录数组最长上升子序列的长度
            int maxLength = dp[0];
            // 遍历数组中每个元素
            for (int i = 1; i < nums.length; i++) {
        
                // maxValue 即为 dp[i] 的值，默认为 1，即默认前面的元素都比 num[i] 大
                int maxValue = 1;
                // 循环遍历 nums[0]~nums[i-1]
                for (int j = 0; j < i; j++) {
        
                    // 如果 nums[j] 放在 nums[i] 后面能够组成上升序列，则记录此时 dp[j]+1 的值
                    // 但是，只记录单个 dp[j]+1 的值并不够，我们需要记录满足条件的所有 dp[i]+1 的最大值
                    if (nums[j] < nums[i]) {
        
                        maxValue = Math.max(maxValue, dp[j] + 1);
                    }
                }
                // dp[i] 的最大值
                dp[i] = maxValue;
                // 记录此时的最长上升子序列的长度
                maxLength = Math.max(maxLength, dp[i]);
            }
            return maxLength;
        }
    }

[image-20200906125916097]: /images/20221123/aecaf37520ed480f970fc16cb93e23f3.png