题解 | #最长递增子序列#

import java.util.Scanner;
import java.util.Stack;
import java.util.TreeMap;
public class Main
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int len = scanner.nextInt();
        int[] dp = new int[len];
        int[] data = new int[len];
        int ans=0;
        int flag = 0;//当前最长序列
        TreeMap<Integer,Integer> map = new  TreeMap<Integer,Integer>();//（长度为i的最小结尾数, 序列长度i)
        for(int i=0;i<len;i++){
            Integer key = map.ceilingKey(data[i]);
            if(key == null){//没找到ceiling，说明当前data是最大的，添加一个键值对，序列长度加1
                map.put(data[i],++flag);
                dp[i] = flag;
            }else{//找了，更新，（键1，值1）替换成（键2，值1)
                dp[i] = map.get(key);
                map.remove(key);
                map.put(data[i],dp[i]);
            }
            ans = Math.max(ans, dp[i]);
 
        }
        Stack<Integer> ANS = new Stack<>();
        for(int i=len-1;i>=0;i--)
        {
            if(dp[i]==ans)
            {
                ANS.push(data[i]);
                ans--;
            }
        }
        while(!ANS.empty())
        {
            System.out.print(ANS.pop()+" ");
        }
    }
}