25 最长递增子序列 - 程序员代码面试指南

```java
import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    // 最左边大于等于val的数
    static int bsearch(int[] ends, int left, int right, int val){
        if(ends[right] < val){
            return -1;
        }
        while (left <= right){
            int mid = (left + right) / 2;
            if(ends[mid] <= val){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++){
            arr[i] = sc.nextInt();
        }
        // ends[b] = c 表示遍历到目前为止 长度为b+1的递增序列中，最小的结尾数 c
        // ends[] 是一个递增的数组，适合二分法
        int[] ends = new int[n];
        // dp[i] 以 i 位置结束的最长递增长度
        int[] dp = new int[n];
        dp[0] = 1;
        ends[0] = arr[0];
        // 有效区域为[0, right]; right + 1 为 最长递增
        int right = 0;
        for(int i=1;i<n;i++){
            int pos = bsearch(ends,0, right, arr[i]);
            if(pos == -1){ //  arr[i] 当前最大
                right = right + 1;
                ends[right] = arr[i];
                dp[i] = right + 1;
            }else{
                right = Math.max(right, pos);
                // pos + 1 长度的最长递增 结尾的就是 arr[i]
                ends[pos] = arr[i];
                dp[i] = pos + 1;
            }
        }
        int maxLen = right + 1; // 最长递增的长度
        int lastDpVal = maxLen + 1;
        int[] ans = new int[maxLen];
        int ansIndex = maxLen - 1;
        // dp值相同的话，显然最右边的值最小；否则dp值就不该相等
        for(int i=n-1;i>=0;i--){
            if(lastDpVal == 0){
                break;
            }
            if(dp[i] == lastDpVal - 1){
                ans[ansIndex--] = arr[i];
                lastDpVal --;
            }
        }
        for(int i=0;i<maxLen-1;i++) {
            System.out.print(ans[i] + " ");
        }
        System.out.println(ans[maxLen-1]);
    }

}
/*
9
2 1 5 3 6 4 8 9 7

1 3 4 8 9

5
1 2 8 6 4

1 2 4
*/
ac
