设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

输入格式:

输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开

输出格式:

最长单调递增子序列的长度

输入样例:

在这里给出一组输入。例如：

5
1 3 5 2 9

输出样例:

在这里给出相应的输出。例如：

4

想到的思路是从前往后填表的方式，m表记录当前位置的最长子序列。

AC代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //输入n
        String str1 = sc.nextLine();
        int n = Integer.parseInt(str1);
        String str = sc.nextLine();

        //输入n个数
        String[] s = str.split(" ");
        int[] num = new int[n];
        for (int i = 1; i < n; i++) {
            num[i] = Integer.parseInt(s[i]);
        }

        //m[i]表示从num[0]到num[i]的最长子序列
        int[] m = new int[n];
        //max实时记录最长子序列
        int max = 0;
        //先将m[0]即num[0]单独表示为最长子序列1，便于后面的比较
        m[0] = 1;

        //从num[1]开始，num[0]到num[i]的最长子序列
        for (int i = 1; i < n; i++) {
            //记录当前序列长度
            int l = 0;

            //找num[0]到num[i]的最长子序列
            for (int j = 0; j < i; j++) {
                if (m[j] > l && num[j] < num[i]) {
                    l = m[j];
                }
            }
            m[i] = l + 1;
            max = Math.max(max, m[i]);
        }
        System.out.println(max);
    }
}