解1：最长递增子序列长度：动态规划
题目来源：[NC]163. 最长上升子序列(一)
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
👉定义 
：以下标为 
结尾的最长上升子序列的长度，注意 
必须被选取。
从小到大计算
数组的值，在计算
之前，我们已经计算出
的值
状态转移方程：
最后，整个数组中的最长上升子序列即所有 
中的最大值。
复杂度分析
时间复杂度：
，其中 
为数组 
的长度。
动态规划的状态数为 
，计算状态 
时，需要 
的时间遍历 
的所有状态
空间复杂度：
，需要额外使用长度为 
的 
数组。
我的代码
public class Solution {//状态转移方程：nums[i]>nums[j]&&dp[i]=max{dp[i],dp[j]+1}public static int lengthofLIS(int[] nums){int n=nums.length;int[]dp=new int[n];int res=0;for (int i = 0; i < n; i++) {dp[i]=1;for (int j = 0; j <i; j++) {if(nums[i]>nums[j])dp[i]=Math.max(dp[i],dp[j]+1);}res=Math.max(res,dp[i]);}return res;}}
解1：最长递增子序列长度：贪心+二分
题目来源：[NC]164. 最长上升子序列(二)
（贪心：）要使上升子序列尽可能的长，则我们希望每次在上升子序列最后加上的那个数尽可能的小。基于上面的贪心思路，我们维护一个数组 
。
👉定义 
：存放长度为 
的最长上升子序列的末尾元素的最小值，
记录目前最长上升子序列的长度
同时我们可以注意到
是关于
单调递增的，因此可以通过二分查找来快速插入
🚩最后整个算法流程为：从前往后遍历数组 
，在遍历到 
时：
- **如果 ** ，则直接加入到数组末尾 ，并更新 ；- **否则** 在  数组中二分查找，找到第一个比  小的数  ，并更新 。
🍗重点：以输入序列 [0, 8, 4, 12, 2] 为例： 第一步插入 0， d = [0]； 第二步插入 8， d = [0, 8]； 第三步插入 4， d = [0, 4]； 第四步插入 12，d = [0, 4, 12]； 第五步插入 2 ， d = [0, 2, 12]。
解释：为什么可以直接找到第一个比
小的数
，并更新
？ 因为从前往后遍历数组
，
一定比
中数字后出现，只要比它大就可以构成递增序列
复杂度分析
时间复杂度：
，其中 
为数组 
的长度。
- 遍历数组个数为 ，每次二分查找需要  的时间
，需要额外使用长度为 
的 
数组。
我的代码
class Solution {
public int lengthOfLIS(int[] nums) {
int len = 1, n = nums.length;
if (n == 0) return 0;
int[] d = new int[n + 1];
d[len] = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) {
d[++len] = nums[i];
} else {
// 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
int l = 1, r = len, pos = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
}
}
return len;
}
}
解2：最长递增子序列的具体序列：贪心+二分
题目来源：[NC]91. 最长上升子序列(三)
给定数组 
，设长度为 
，输出 
的最长上升子序列。
（若有多个答案，输出其中 按数值
(注：区别于按单个字符的ASCII码值)进行比较的，字典序最小 的那个）
要求：空间复杂度 
，时间复杂度 
示例1：
输入：[2,1,5,3,6,4,8,9,7] 返回值：[1,3,4,8,9]
示例2：
输入：[1,2,8,6,4] 返回值：[1,2,4] 说明： 其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个 按数值进行比较的字典序 最小，故答案为（1，2，4）
我们知道求解最长递增子序列问题有两种：
- 动态规划
- 贪心+二分
由于本题空间和时间复杂度的要求，故而使用贪心+二分，解题分为两步走：
第一步——求最长递增子序列长度
求解出来的
其实就是以当前 
结尾的递增子序列的最大长度第二步——求字典序靠前的子序列
假设原始数组是
，得到的 
为 
，最终输出结果为 
（字典序最小的最长递增子序列），
的最后一个元素在 
中位置无庸置疑是 
对应的下标，那么到底是 
还是 
呢？如果是 
，那么 
，则 
，与已知条件相悖。因此我们应该取 
放在 
的最后一个位置。也就是说相同的 
靠后的才是字典序小的 。
👉定义 
：存放长度为 
的最长上升子序列的末尾元素的最小值，
记录目前最长上升子序列的长度
👉定义 
：存放以下标 
为结尾的递增子序列的最大长度
复杂度分析
时间复杂度：
，其中 
为数组 
的长度。
- 遍历数组个数为 ，每次二分查找需要  的时间
空间复杂度：
- 需要额外使用长度为  的  数组，以及长度为 ** **的  数组。
我的代码
public class Solution {
//状态转移方程：nums[i]>nums[j]&&dp[i]=max{dp[i],dp[j]+1}
public int[] LIS (int[] nums) {
//1. 初始化
int len = 1, n = nums.length;
if (n == 0) return null;
int[] d = new int[n + 1];
int[]dp=new int[nums.length];
Arrays.fill(dp,1);
d[len] = nums[0];
//2. 依次遍历查找元素
for (int i = 1; i < n; ++i) {
//3. 当前元素能够续接上
if (nums[i] > d[len]) {
d[++len] = nums[i];
dp[i]=len;
} else {
// 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
int l = 1, r = len, pos = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
dp[i]=pos+1;
}
}
//new出新的答案数组
int[]ans=new int[len];
for(int i=dp.length-1;i>=0;i--){
if(len==dp[i]){
ans[--len]=nums[i];
}
}
return ans;
}
}
解3：最长递增子序列的序列个数：动态规划
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 1:
输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
👉定义 
：以下标为 
结尾的最长上升子序列的长度，注意 
必须被选取。
👉定义 
：以下标为 
结尾的最长上升子序列的个数， 注意 
必须被选取。
设 
的最长上升子序列的长度为 
，那么答案为所有满足 
的 
所对应的
之和。
🔖我们从小到大计算 
数组的值，在计算 
之前，我们已经计算出 
的值
状态转移方程：
即 
时考虑往 
中最长的上升子序列后面再加一个 
。
对于 
，其等于所有满足 
的 
之和。
复杂度分析
时间复杂度：
，其中 
为数组 
的长度 。
空间复杂度：
。
我的代码
public int findNumberOfLIS(int[] nums) {
//1. 初始化
int n = nums.length, maxLen = 0, ans = 0;
int[] dp = new int[n];
int[] cnt = new int[n];
Arrays.fill(dp,1);
Arrays.fill(cnt,1);
//2. 状态转移
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
//若 nums[i] > nums[j],查看是否能刷新最长长度
if (nums[i] > nums[j]) {
//若能刷新,首次路径
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
cnt[i] = cnt[j]; // 重置计数
} else if(dp[j] + 1 == dp[i]){
cnt[i] += cnt[j]; // 多条路径,路径数相加
}
}
}
//3. 中途保存答案
if (dp[i] > maxLen) {
maxLen = dp[i];
ans = cnt[i]; // 重置计数
} else if (dp[i] == maxLen) {
ans += cnt[i];
}
}
return ans;
}
解4：所有具体的递增子序列：递归+剪枝
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
示例 1：
输入：nums = [4,6,7,7] 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：
输入：nums = [4,4,3,2,1] 输出：[[4,4]]
我们可以采取最朴素的思路，即枚举出所有的子序列，然后判断当前的子序列是否是非严格递增的。
那么我们可以用什么办法来枚举所有的子序列呢？
对于原序列的每一个数来说，都有两种可能的状态，即被选中或者不被选中。如果我们用 
代表被选中，
代表不被选中，假设一个序列长度为 
，那么选出的子序列就对应着下面的八种状态：
[0, 0, 0] [0, 0, 1] [0, 1, 0] [0, 1, 1] [1, 0, 0] [1, 0, 1] [1, 1, 0] [1, 1, 1]
那么我们可以用什么办法来判断所有的重复子序列呢？
我们可以使用 
表，
编码使用 Rabin-Karp 编码
算法说明：
我们使用递归枚举子序列
- 临时数组
：用来保存当前选出的子序列 
：用来表示当前位置的下标，在执行 
时，我们需要考虑 
这个位置选或者不选 。在
执行开始前，说明 
这个区间内的所有元素都已经被考虑过，而 
这个区间内的元素还未被考虑。
- 如果选择当前元素，那么把当前元素加入到
中，然后递归下一个位置，在递归结束后，应当把
的最后一个元素删除进行回溯 - 如果不选当前的元素，直接递归下一个位置。
当然，如果我们简单地这样枚举，对于每一个子序列，我们还需要做一次 
的合法性检查和哈希判重复，在执行整个程序的过程中，我们还需要使用一个空间代价 
的哈希表来维护已经出现的子序列的哈希值。我们可以对选择和不选择做一些简单的限定，就可以让枚举出来的都是合法的并且不重复：
使序列合法的办法非常简单，即给「选择」做一个限定条件
只有当当前的元素大于等于上一个选择的元素的时候才能选择这个元素，即
，这样枚举出来的所有元素都是合法的递增序列。使序列不重复的办法非常简单，我们需要给「不选择」做一个限定条件
只有当当前的元素不等于上一个选择的元素的时候，才考虑不选择当前元素，直接递归后面的元素。因为如果有两个相同的元素，我们会考虑这样四种情况：
- 前者被选择，后者被选择
- 前者被选择，后者不被选择 (舍弃)
- 前者不被选择，后者被选择
- 前者不被选择，后者不被选择
其中第二种情况和第三种情况其实是等价的，我们这样限制之后，舍弃了第二种，保留了第三种，于是达到了去重的目的。
复杂度分析
时间复杂度：
，其中 
为数组 
的长度 。
- 仍然需要对子序列做二进制枚举，枚举出的序列虽然省去了判断合法性和哈希的过程，但是仍然需要  的时间添加到答案中。
空间复杂度：
。
- 临时数组使用的空间代价是 ，递归使用的栈空间的空间代价也是 。
我的代码
class Solution {
//1. 临时数组
List<Integer> temp = new ArrayList<Integer>();
//2. 结果集
List<List<Integer>> ans = new ArrayList<List<Integer>>();
//3. 从0开始执行递归
public List<List<Integer>> findSubsequences(int[] nums) {
dfs(0, Integer.MIN_VALUE, nums);
return ans;
}
public void dfs(int cur, int pre, int[] nums) {
//如果到达序列末尾,并且长度大于2合法,加入答案
if (cur == nums.length) {
if (temp.size() >= 2) {
ans.add(new ArrayList<Integer>(temp));
}
return;
}
//未到达末尾,当前元素大于等于上一个元素,可以加入属于合法元素
if (nums[cur] >= pre) {
temp.add(nums[cur]); //【选择】临时数组加入当前元素
dfs(cur + 1, nums[cur], nums); //递归下一个元素,pre变成当前元素
temp.remove(temp.size() - 1); //【不选择】移除当前元素
}
if (nums[cur] != pre) { //如果当前元素和上一个元素不重复
dfs(cur + 1, pre, nums); //直接递归下一个元素
}
}
}
若有收获，就点个赞吧
0 人点赞
