题解 | #最长上升子序列(一)#

题目主要信息:

• 给定一个数组，求其中最长的严格上升子序列的长度
• 子序列是指数组去掉或不去掉元素后的数组，不要求在原本数组中全部相邻，但是在原数组中的相对位置不能改变
• 严格上升指子序列严格单调递增

举一反三：

学习完本题的思路你可以解决如下题目：

BM65 最长公共子序列(二)

BM66.最长公共子串

BM73 最长回文子串

BM75 编辑距离(一)

BM76 正则表达式匹配

BM77 最长的括号子串

方法：动态规划（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

思路：

要找到最长的递增子序列长度，每当我们找到一个位置，它是继续递增的子序列还是不是，它选择前面哪一处接着才能达到最长的递增子序列，这类有状态转移的问题常用方法是动态规划。

具体做法：

• step 1：用$dp[i]dp[i]$表示到元素$ii$结尾时，最长的子序列的长度，初始化为1，因为只有数组有元素，至少有一个算是递增。
• step 2：第一层遍历数组每个位置，得到n个长度的子数组。
• step 3：第二层遍历相应子数组求对应到元素$ii$结尾时的最长递增序列长度，期间维护最大值。
• step 4：对于每一个到$ii$结尾的子数组，如果遍历过程中遇到元素j小于结尾元素，说明以该元素结尾的子序列加上子数组末尾元素也是严格递增的，因此转移方程为$dp[i]=dp[j]+1dp[i]\; =\; dp[j]\; +\; 1$。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public int LIS (int[] arr) {
        int[] dp = new int[arr.length];
        //设置数组长度大小的动态规划辅助数组
        Arrays.fill(dp, 1); 
        int res = 0;
        for(int i = 1; i < arr.length; i++){
            for(int j = 0; j < i; j++){
                //可能j不是所需要的最大的，因此需要dp[i] < dp[j] + 1
                if(arr[i] > arr[j] && dp[i] < dp[j] + 1){
                    //i点比j点大，理论上dp要加1
                    dp[i] = dp[j] + 1; 
                    //找到最大长度
                    res = Math.max(res, dp[i]); 
                }
            }
        }
        return res;
    }
}

C++实现代码：

class Solution {
public:
    int LIS(vector<int>& arr) {
        //设置数组长度大小的动态规划辅助数组
        vector<int> dp(arr.size(), 1); 
        int res = 0;
        for(int i = 1; i < arr.size(); i++){
            for(int j = 0; j < i; j++){
                //可能j不是所需要的最大的，因此需要dp[i] < dp[j] + 1
                if(arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                    //i点比j点大，理论上dp要加1
                    dp[i] = dp[j] + 1; 
                    //找到最大长度
                    res = max(res, dp[i]); 
                }
            }
        }
        return res;
    }
};

Python代码实现：

class Solution:
    def LIS(self , arr: List[int]) -> int:
        #设置数组长度大小的动态规划辅助数组
        dp = [1 for i in range(len(arr))] 
        res = 0
        for i in range(1, len(arr)):
            for j in range(i):
                #可能j不是所需要的最大的，因此需要dp[i] < dp[j] + 1
                if arr[i] > arr[j] and dp[i] < dp[j] + 1: 
                    #i点比j点大，理论上dp要加1
                    dp[i] = dp[j] + 1 
                    #找到最大长度
                    res = max(res, dp[i]) 
        return res

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，其中$nn$为数组长度，两层遍历循环
• 空间复杂度：$O(n)O(n)$，辅助数组dp的空间