最长上升子序列【DP】

状态表示

f[i] ：以 a[i] 结尾的所有上升序列的最大值

状态计算

划分依据

根据状态计算的理论，“只从最后一个不同的点“开始分析，根据状态表示可以知道”以 a[i] 结尾的所有上升序列的最大值“，a[i]是相同的，所以a[i]用1来代替。
计算以a[i]结尾的和不以a[i]结尾的最大值
在计算每一个f[i]的时候，都和其他f[1～i-1]进行比较，就可以得到一个当前的最大值

public class MaxLengthNum {
    static int[] w = new int[1001];
    static int[] f = new int[1001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numsLength = sc.nextInt();
        for (int i = 1; i <= numsLength; i++) {
            w[i] = sc.nextInt();
        }
        int max = 1;
        for (int i = 1; i <= numsLength ; i++) {
            f[i] = 1;
            for (int j = 1; j < i ; j++) {
               if (w[i]>w[j]){
                   f[i] = Math.max(f[i], f[j] + 1);
               }
            }
            max = Math.max(f[i],max);
            System.out.println(f[i]);
        }
        System.out.println(max);
    }
}