题解 | #Redraiment的走法#

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

public class Main {
    public static void main(String[] args) {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String a;
        int[] num;
        int max, n;
        try {
            a = in.readLine();
            n = parse(a);
            num = new int[n];
            a = in.readLine();
            parseArr(a, num);
            in.close();
        } catch (IOException e) {
            e.printStackTrace();
            throw new RuntimeException(e);
        }
        max = redraiment(num, n);
        System.out.print(max);
    }

    static int redraiment(int[] num, int n) {
        int[] dp = new int[n];// 考虑每个元素后的对应升序长度
        int[] a1 = new int[n];// 升序子序列
        int i, len = 1, left, right, mid;
        a1[0] = num[0];// 第一个元素是原序列的第一个元素
        dp[0] = 1;
        for (i = 1; i < n; i++) {
            if (a1[len - 1] < num[i]) {
                a1[len++] = num[i];// 相应的升序数组a1长度+1
                dp[i] = len;
            } else {
                left = 0;
                right = len - 1;
                while (left < right) {// 二分法
                    mid = (left + right) >> 1;
                    if (a1[mid] >= num[i]) // 中间的值大于原序列该元素
                        right = mid;
                    else
                        left = mid + 1;
                }
                a1[left] = num[i];// 子序列中替换第一个比该位大的值
                dp[i] = left + 1;
            }
        }
        int[] res = new int[len];// 最终的最长升序子序列
        for (i = n - 1; i >= 0; i--) {// 逆序遍历dp状态数组
            if (dp[i] ==
                    len)// 如果dp该位的值=子序列长度，表示原序列中该位的值是最长子序列中的一个值
                res[--len] = num[i];//长度-1
        }
        return res.length;
    }

    static int parse(String a) {
        int i = 0, n = 0, l = a.length();
        char[] chrAy = new char[l];
        a.getChars(0, l, chrAy, 0);
        while (i < l) {
            if ((chrAy[i] - '0' | '9' - chrAy[i]) > 0) {
                n *= 10;
                n += chrAy[i] - '0';
            }
            i++;
        }
        return n;
    }

    static void parseArr(String a, int[] arr) {
        int i = 0, j = 0, n = 0, l = a.length();
        char[] chrAy = new char[l];
        a.getChars(0, l, chrAy, 0);
        while (i < l) {
            if (chrAy[i] == ' ') {
                arr[j++] = n;
                n = 0;
            } else {
                if ((chrAy[i] - '0' | '9' - chrAy[i]) > 0) {
                    n *= 10;
                    n += chrAy[i] - '0';
                    if (i == l - 1)
                        arr[j++] = n;
                }
            }
            i++;
        }
    }
}