题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n)$

Java 代码

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

public class Main{
    private static int N;
    private static int[] f;
    private static int[] a;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{
        String[] s1 = read.readLine().split("\\s+");
        N = Integer.parseInt(s1[0]); // 行数
        f = new int[N+1];  
        a = new int[N+1];

        String[] s2 = read.readLine().split("\\s+");
        for(int i = 1; i <= N; i++){
            a[i] = Integer.parseInt(s2[i-1]);
        }

        for(int i = 1; i <= N; i++){
            f[i] = 1;
            for(int j = 1; j < i;j++){
                if(a[j] < a[i]){
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }

        int res = 0;
        for(int i = 1; i <= N; i++){
            res = Math.max(f[i], res);
        }

        System.out.println(res);
    }

}