题目描述

最长上升子序列

JAVA 代码

import java.util.*;
import java.io.*;

class Main{
    static int N = 1010;
    static int[] a = new int[N], f = new int[N];

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for(int i=1;i<=n;i++){
            a[i] = sc.nextInt();
        }

        for(int i=1;i<=n;i++){
            //只包含当前节点的最大长度
            f[i] =1;
            for(int j=1; j<=n;j++){
                //如果当前节点比上一个节点大.
                //则 上个节点的值 +1 则等于当前节点的长度. 
                if(a[i]> a[j])f[i] = Math.max(f[i], f[j]+1);
            }
        }
        int res = 0 ;
        for(int i=1;i<=n;i++)res = Math.max(res, f[i]);
        System.out.println(res);
    }
}