题解 | #最长上升子序列(三)#（最详细易懂的解释）
最长上升子序列(三)
https://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481
描述
给定数组 arr ，设长度为 n ，输出 arr 的最长上升子序列。（如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）
数据范围：0 \le n \le 200000 , 0 \le arr_i \le 10000000000≤n≤200000,0≤arri≤1000000000要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
示例1
输入：
[2,1,5,3,6,4,8,9,7]
返回值：
[1,3,4,8,9]
可能会遇到的疑问解释：
1，替换的主要作用就是，找到arr当前的元素，在temp中的位置，从而确定它的长度。 比如temp数组元素为[2,4,6],
而arr中当前元素为5，那temp中第一个大于5的元素就是6，那5的长度就是3 。同时替换掉后，也能不影响后续元素位置的
判定。
2，因为当arr数组的当前元素 ，小于temp数组的最后一个元素时，只是替换temp中的元素，而不增加，因此不更新max值
3，要从后往前遍历，比如arr数组为[2,5,3,6,4] ,对应的元素长度 len数组为[1,2,2,3,3] ,根据题意得到的 字典序最小的 最长子序列应该是[2,3,4] ，
而通过从后往前遍历就可以实现，原理是，后面小的元素会替换前面大的元素，所以相同长度下，一定是后面的元素更小。
代码注释
#如果重上一次大学你会换专业吗#import java.util.*;
public class Solution {
/**
* retrun the longest increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型一维数组
*/
public int[] LIS (int[] arr) {
// write code here
int n = arr.length;
// 定义一个数组，用来维护一个当前最长的子序列
int[] temp =new int[n];
// 定义一个数组len，用来记录每个元素当前的长度
int[] len = new int[n];
// 定义一个变量 max ，用来记录temp中最长的子序列长度
int max =0;
for(int i=0;i<n;i++){
// 当temp为空时，先放入arr中第一个元素， 有了第一个元素后， 只有当arr中元素大于temp
// 才把其添加到temp数组中
// max-1 是因为，每次temp中添加完数据，记录最大值的max要加一，比如temp为空时，
// 添加一个数据，max变为1，但其实添加的元素在temp中下标为0，temp[0]才是当
// 前temp中最后一个元素
if(i==0 || temp[max-1]<arr[i]){
// 每次添加一个数组到temp数组中，就给max加一
temp[max++]=arr[i];
// 记录长度的len数组，就记录当前arr数组元素的长度
len[i]= max;
}else{
// 如果arr数组中当前元素小于temp中最后一个元素，那就找到temp中第一个大于arr数组的元素，
// 然后将其替换掉（看上面疑问解释1）
int index = search(temp,max,arr[i]);
temp[index]= arr[i];
// 替换后，更新arr数组中当前元素的长度。 但是不更新 max 值（看上面疑问解释2 ）
len[i]=index +1;
}
}
// 最后用一个新的数组，从后往前遍历arr数组，拿到字典序最小的 最长子序列（看上面疑问解释3 ）
int[] res = new int[max];
for(int i=n-1;i>=0;i--){
// 当max与当前元素的长度相同，就把它放入res数组中
if(len[i] == max)
// 长度比下标大一，所以要先减一
res[--max] = arr[i];
}
return res;
}
public int search(int[] temp,int max,int arrI){
int left = 0;
int right = max-1;
while(left<right){
int mid = left+(right-left)/2;
if(temp[mid]>= arrI){
right = mid;
}else{
left = mid+1;
}
}
return left;
}
}
