目录
题目：
输入描述:
输出描述:
示例1
输入
输出
示例2
输入
输出
说明
备注:
思路分析：
改进：
得到最长子序列：
易错点：
代码展示：
题目：
给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
输入描述:
输出两行，第一行包括一个正整数n（n<=100000），代表数组长度。第二行包括n个整数，代表数组arr 。 (1 ≤ arr[i] ≤ 1e9)
输出描述:
输出一行。代表你求出的最长的递增子序列。
示例1
输入
9 2 1 5 3 6 4 8 9 7
输出
1 3 4 8 9
示例2
输入
5 1 2 8 6 4
输出
1 2 4
说明
其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）
备注:
时间复杂度O(NlogN)，空间复杂度O(N)。
思路分析：
由递增子序列，可以知道该序列是依赖与前面序列，且连续性要求较高 所以dp[i]存储的值是以array[i]元素结尾时的最优解，即最长递增子序列dp[i]点最长子序列依赖于所有array[小于i的值]的dp[]值中的最大值 比如array = {1,3,5,4,6,5,7}dp[]的前三位是{1,2,3} 则第dp[3]，查到array[0]而dp[1]>dp[0] 所以将dp[3]赋值为dp[1]+1,因为前三位中有个长度为2的序列的结尾数比array[3]小依次更新dp,找到dp的最大值，即为最长递增子序列的长度改进：
每次求dp都要遍历一次array的前面部分，导致时间复杂度时O(N^2)但是之前的array与dp已经遍历过了，现在我们要做的是将其中重要的信息存储起来 重要信息:长度为0/1/2/3的子序列，最小要以什么array结尾每次dp的更新就不需要去遍历所有array， 需要查找到合适的结尾数，在其基础上将序列长度加一。并根据当前dp，array更新“重要信息”序列长度，与结尾数的映射一定是单调递增的，所以，查找时，可以用二分查找，或者用有序表来组织（ceilingKey()方法）得到最长子序列：
根据dp，dp存储的是以dp[i]结尾时的最长子序列长度，那么倒序遍历dp，当dp[i]的值等于len,len-1,len-2....时说明是最长子序列的最小字典序易错点：
在用有序表TreeMap时，如果要将（键1，值1）替换成（键2，值1)，不能单纯使用replace，put方法，要先remove（键1，值1），再put(键2，值1)代码展示：
import java.io.*;import java.util.TreeMap;public class Main{public static void main(String[] args)throws IOException{BufferedReader read = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(read.readLine());String[] str = read.readLine().split(" ");int dp[] = new int[n];//以array[i]结尾的序列的最长长度int array[] = new int[n];for(int i=0;i<n;i++){array[i] = Integer.parseInt(str[i]);dp[i] = 0;}int max = 0;//最长子序列长度int flag = 0;//当前最长序列TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();//（长度为i的最小结尾数, 序列长度i)for(int i=0;i<n;i++){Integer key = map.ceilingKey(array[i]);if(key == null){//没找到ceiling，说明当前array是最大的，添加一个键值对，序列长度加1map.put(array[i],++flag);dp[i] = flag;}else{//找了，更新，（键1，值1）替换成（键2，值1)dp[i] = map.get(key);map.remove(key);map.put(array[i],dp[i]);}max = Math.max(max, dp[i]);}//System.out.println(max);String sout = "";for(int j = n-1;j>=0;j--){//倒序遍历，遇到len,len-1,len-1...将其加入字符串if(dp[j] == max){sout = array[j]+" "+sout ;max--;}}System.out.print(sout);}}
