解题思路

动态规划方法，用长度n的dp记录所有元素的序列长度、序列末尾数字。首个dp值长度为1，末尾值为6。
后面的元素算dp时要遍历前面的dp点，找出最长并且序列末尾小于arr[i]，可以添加在后面的dp点，长度+1。如果找不到，就添加一个长度1的dp点。添加时末尾序列改为arr[i]。
为了方便遍历，dp按序列长度从大到小排序。目前这个解题过程较乱，不好通过文字描述清楚，代码注释尽量详细写了过程。算法上也还有优化空间。

代码 

import java.util.Scanner;
import java.util.LinkedList;
import java.util.List;
 
public class Main{
     
    public static void main(String[] args){
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] a = new int[n];
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        // dp记录<上升序列的末尾数字, 该序列长度>，按长度排序
        // <num, length>
        List<DP> dp = new LinkedList<>();

        dp.add(0, new DP(a[0], 1));

        for (int i = 1; i < n; i++) {
            // 前面记录的dp中是否有比a[i]小的数字
            boolean hasSmall = false;
            for (int j = 0; j < dp.size(); j++) {
                if (dp.get(j).num < a[i]) {
                    // 前面dp中有比a[i]小的数字，并且dp是按长度排序的，此处一定是最大子序列
                    int length = dp.get(j).length + 1;    // 序列长度+1
                    for (int k = 0; k < dp.size(); k++) {
                        // 插入dp时，按照length长度从大到小顺序插入
                        if (!(dp.get(k).length > length)) {
                            dp.add(k, new DP(a[i], length));
                            break;
                        }
                    }
                    hasSmall = true;
                    break;
                }
            }

            // 前面dp中没有比a[i]小的数字，把a[i]记为长度1
            if (!hasSmall) {
                dp.add(dp.size(), new DP(a[i], 1));
            }
        }
        
        System.out.println(dp.get(0).length);
    }
    
    public static class DP {
        public int num;
        public int length;

        public DP(int num, int length) {
            this.num = num;
            this.length = length;
        }
    }
}