这道题在LeetCode和牛客上都存在，且是各大算法刷题必出现的题。对于我而言确实有点难度。目前大致理解了，学习记录下。
对于LeetCode中比较简单，求的是最长递增子序列的长度；牛客中求的是子序列本身。
首先看下求长度问题：
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
因为是求长度问题，所以我们需要辅助空间记录其长度。又因为这个序列可能如下情况:
1, 5, 6, 8, 9, 12, 3, 4, 5
如果只用一个空间记录长度，那么记录不了多次的长度问题，所以我们需要用一个数组来记录从左到右依次扫描到每个元素时候的上升子序列的长度。
由于所求上升，故而我们需要依次判断当前元素和前面的所有元素的大小关系，然后再累加其对应的长度即可。
public int lengthOfLIS(int[] nums) {
if(nums.length == 0) return 0;
int[] dp = new int[nums.length];
int maxLen = 1;
dp[0] = 1;
for(int i=1;i<nums.length;i++){
dp[i] = 1;
for(int j=0;j<i;j++){
if(nums[j] < nums[i]){
dp[i] = Math.max(dp[j]+1, dp[i]);
}
}
maxLen = Math.max(dp[i], maxLen);
}
return maxLen;
}
按照官方的题解，这个题可以使用贪心 + 二分查找来进行优化。可以引入一个额外的辅助数组空间，用下标表示其对应的长度，如果当前元素很小，就需要查找，放置在最开始位置，并更新dp值为当前元素在辅助空间中的下标。也就是说，新引入一个辅助空间用来更新dp数组。
public int lengthOfLIS(int[] arr) {
if(arr.length == 0) return 0;
int n = arr.length;
int[] end = new int[n + 1];
int[] dp = new int[n];
int len = 1;
end[1] = arr[0];
dp[0] = 1;
int maxLen = 1;
for (int i = 0; i < n; i++) {
if (end[len] < arr[i]) {
end[++len] = arr[i];
dp[i] = len;
} else {
int l = 1;
int r = len;
while (l <= r) {
int mid = (l + r) >> 1;
if (end[mid] >= arr[i]) {
r = mid - 1;
} else l = mid + 1;
}
end[l] = arr[i];
dp[i] = l;
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
然后，看下牛客网中的这个题，描述为：
给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
输入：
[1,2,8,6,4]
返回值：
[1,2,4]
说明：
其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）
为了解决这个问题，我们可以从dp数组入手，比如下面的案例：
1,2,0,8,7, 12, 4
dp数组为：1 2 1 3 3 4 3
那么我们从右到左开始遍历，如果等于长度len，那么我们就取出元素，依次为：
12, 7, 2, 1，也即是：1， 2， 7， 12
public int[] LIS(int[] arr) {
if(arr.length == 0) return null;
int[] dp = new int[arr.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < arr.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxans = Math.max(maxans, dp[i]);
}
int[] res = new int[maxans];
for (int i = arr.length - 1; i >= 0; i--) {
if (dp[i] == maxans) {
res[--maxans] = arr[i];
}
}
return res;
}
但是，这个在牛客网会超时。
public int[] LIS(int[] arr) {
int n = arr.length;
int[] end = new int[n + 1];
int[] dp = new int[n];
int len = 1;
end[1] = arr[0];
dp[0] = 1;
for (int i = 0; i < n; i++) {
if (end[len] < arr[i]) {
end[++len] = arr[i];
dp[i] = len;
} else {
int l = 1;
int r = len;
while (l <= r) {
int mid = (l + r) >> 1;
if (end[mid] >= arr[i]) {
r = mid - 1;
} else l = mid + 1;
}
end[l] = arr[i];
dp[i] = l;
}
}
int[] res = new int[len];
for (int i = n - 1; i >= 0; i--) {
if (dp[i] == len) {
res[--len] = arr[i];
}
}
return res;
}
测试通过。
也就是重点在于dp数组的构建，然后我们根据最大长度从右到左遍历，存储第一次出现的长度的数组的元素即可。
