1. 概念
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列，但[3,0]就不是子序列。
2. 最长子序列
2.1 最长递增子序列
题目：
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
例如：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4
输入：nums = [7,7,7,7,7,7,7]
输出：1
思路一：
- dp[i]用来表示以arr[i]结尾的最长递增子序列，
- dp[0]=1
- dp[i] 和 dp[i-1] 之间的关系，还是和之前dp数据都有关系？
- 如果 arr[i] > arr[0]...arr[k]...arr[i-1] 那么对应dp[i] = dp[k] + 1，然后求最大值，即dp[i] = max{dp[k]+1}
- 如果 arr[i] <= arr[k]，dp[i] = max{dp[k]}
- 返回Max{dp[0 ~ arr.length-1]}就是最长递增子序列的答案
时间复杂度：O(n^2)
private int process(int[] arr){
//1. dp[i] 以arr[i]为结尾的最长的递增子序列的长度
int[] dp = new int[arr.length+1];
//2. 边界
dp[0] = 1;
//3. 转移方程
int max = Integer.MIN_VALUE;
for (int i = 1; i < arr.length; i++) {
int maxLength = Integer.MIN_VALUE;
for (int k = 0; k < i; k++) {
if(arr[i] > arr[k]){
maxLength = Math.max(maxLength, dp[k] + 1);
}else {
maxLength = Math.max(maxLength, 1);
}
}
dp[i] = maxLength;
max = Math.max(max, maxLength);
}
return max;
}
思路2:
- 使用dp数组来记录当前递增子序列的元素，那么dp[k] 为长度为k+1的递增子序列的末尾的元素
- 遍历arr数组，在dp中寻找arr[i]的位置：index
- 如果index = dp中当前元素的数量，那么dp中增加arr[i],即dp[index] = arr[i], 同时更新maxLength
- 如果index不等于dp中当前元素的数量（即不是dp的末尾位置），那么也更新dp[index]=arr[i]
- 最后返回maxLength
private int processUpgrade(int[] arr){
//1. dp[k] 为长度为k+1的递增子序列的末尾的元素
int[] dp = new int[arr.length];
//2.
int maxLength = 0;
for (int i = 0; i < arr.length; i++) {
//在dp中二分查找arr[i]的位置
int index = findIndex(dp, maxLength, arr[i]);
//如果index和当前的最大长度相等，符合递增条件，那么就把maxLength+1，并记录当前递增子序列的末尾元素（最大元素）
if(index == maxLength){
maxLength++;
dp[index] = arr[i];
}else {
dp[index] = arr[i];
}
}
return maxLength;
}
private int findIndex(int[] dp, int length, int target){
int s = 0;
int e = length-1;
while (e >= s){
int mid = (s + e)/2;
if(target > dp[mid]){
s = mid + 1;
}else if(target < dp[mid]) {
e = mid - 1;
}else{
return mid;
}
}
return s;
}
2.2 最长递增+1子序列
题目：
给你一个整数数组 nums ，找到其中最长严格递增+1子序列的长度。
例如：
输入：nums = [10,9,1,2,4,7,3]
输出：3
解释：最长递增子序列是 [1,2,3]，因此长度为 3
思路：
- 遍历数据，保存Map<arr[i], index> map1，即 k=10,v=0;k=9,v=1;如果有重复元素，按新index覆盖
- 遍历数据，记录Map<arr[i], length> map2, 其中length为arr[i]结尾的最长严格递增子序列的长度
- 从map1中找arr[i]-1，如果存在且下标为index，判断i>index, 记录：map2<arr[i], length+1>,含义为以arr[i]结尾的最长最长严格递增子序列的长度加了1
- 同时在遍历的过程中更新maxLength，
3.遍历完返回maxLength就是最长严格递增+1子序列的长度
4.同时，如果要求返回数组的话就遍历map2,找到v=maxLength的记录<k,v>，结果就是：[k-maxLength+1, k]；如果有多条相同的记录就是List<[k-maxLength+1, k]>
public int process(int[] arr){
Map<Integer, Integer> map1 = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map1.put(arr[i], i);
}
int maxLength = 0;
for (int i = 0; i < arr.length; i++) {
int tmpLength = 0;
if(map1.containsKey(arr[i]-1)){
Integer index = map1.get(arr[i] - 1);
if(i > index){
tmpLength++;
}
}
maxLength = Math.max(maxLength, tmpLength);
}
return maxLength;
}
public List<List<Integer>> processGetSubArr(int[] arr){
Map<Integer, Integer> map1 = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map1.put(arr[i], i);
}
int maxLength = 0;
Map<Integer, Integer> map2 = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
int tmpLength = 0;
if(map1.containsKey(arr[i]-1)){
Integer index = map1.get(arr[i] - 1);
if(i > index){
tmpLength++;
map2.put(arr[i], tmpLength);
}
}else {
map2.put(arr[i], 1);
}
maxLength = Math.max(maxLength, tmpLength);
}
List<List<Integer>> result = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : map2.entrySet()) {
if(entry.getValue() == maxLength){
List<Integer> tmp = new ArrayList<>();
for (int i = entry.getKey(); i >= entry.getKey() - maxLength + 1 ; i--) {
tmp.add(i);
}
result.add(tmp);
}
}
return result;
}
