题目主要信息:
- 给定一个数组,求其中最长的严格上升子序列的长度
- 子序列是指数组去掉或不去掉元素后的数组,不要求在原本数组中全部相邻,但是在原数组中的相对位置不能改变
- 严格上升指子序列严格单调递增
举一反三:
学习完本题的思路你可以解决如下题目:
方法:动态规划(推荐使用)
知识点:动态规划
动态规划算法的基本思想是:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果
思路:
要找到最长的递增子序列长度,每当我们找到一个位置,它是继续递增的子序列还是不是,它选择前面哪一处接着才能达到最长的递增子序列,这类有状态转移的问题常用方法是动态规划。
具体做法:
- step 1:用表示到元素结尾时,最长的子序列的长度,初始化为1,因为只有数组有元素,至少有一个算是递增。
- step 2:第一层遍历数组每个位置,得到n个长度的子数组。
- step 3:第二层遍历相应子数组求对应到元素结尾时的最长递增序列长度,期间维护最大值。
- step 4:对于每一个到结尾的子数组,如果遍历过程中遇到元素j小于结尾元素,说明以该元素结尾的子序列加上子数组末尾元素也是严格递增的,因此转移方程为。
图示:
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
复杂度分析:
- 时间复杂度:,其中为数组长度,两层遍历循环
- 空间复杂度:,辅助数组dp的空间