最长递增子序列

1. 准备一个长度为maxLen的数组，这时候我们要填最后一个元素，由于arr[maxIdx]是最长递增子序列的最后一个元素，所以先把它填进数组的末尾res[maxLen - 1]。然后maxLen自减（因为已经填完一个元素了）继续往maxIdx的左边前遍历dp数组。
2. 如果遇到dp[i]=maxLen，说明遇到了一个递增子序列长度为maxLen的结尾，再次把arr[i]填入数组的末尾res[maxLen - 1]。然后maxLen自减继续往前遍历dp数组，周而复始就能够填完整个数组。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(strArr[i]);
        }
        int[] dp = new int[n];
        int[] ends = new int[n];
        dp[0] = 1;
        ends[0] = arr[0];
        int tail = 0;      // 有效区域末尾
        int maxLen = 1, maxIdx = 0;    // 最长递增子序列长度和index
        for(int i = 1; i < n; i++){
            int index = lowerbound(ends, 0, tail, arr[i]);
            dp[i] = index + 1;           // 以i结尾的最长递增子序列长度为index+1
            ends[index] = arr[i];
            if(index > tail){
                tail++;                  // 有效区扩充
            }
            if(dp[i] >= maxLen){
                maxLen = dp[i];
                maxIdx = i;
            }
        }
        // 还原字典序最小的最长递增子序列
        int[] increasingSeq = new int[maxLen];
        for(int i = maxIdx; i >= 0; i--){
            // 从后往前更新，遇到递增子序列长度为maxLen的arr[i]就更新结尾位置，然后把maxLen缩短
            if(dp[i] == maxLen){
                increasingSeq[--maxLen] = arr[i];
            }
        }
        for(int i = 0; i < increasingSeq.length; i++){
            System.out.print(increasingSeq[i] + " ");
        }
    }
    
    private static int lowerbound(int[] arr, int L, int R, int target) {
        int left = L, right = R;
        int index = R + 1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(arr[mid] < target){
                left = mid + 1;
            }else{
                index = mid;
                right = mid - 1;
            }
        }
        return index;
    }
}