字节校招面试 手撕代码题

原题链接
https://www.acwing.com/problem/content/897/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;
/*
* 动态规划 f[i] 表示 结尾为i 数值严格单调递增的子序列的最长度值为f[i]
* f[i] = max(f[j] + 1, f[i])
* */

public class Main {
    public static final int N = 1010;

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

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

        // f[i] 仅仅代表以i结尾的子序列的最长长度 并不代表全局的最大值
        int ans = 1;
        int [] f = new int[n + 1];

        for(int i = 0 ; i < n ; i++){
            // 最小长度就是 自己自身
            f[i] = 1;
            for(int j = 0 ; j < i ; j++){
                if(q[i] > q[j]){
                    f[i] = Math.max(f[i],f[j] + 1);
                }
                ans = Math.max(ans,f[i]);    
            }
        }

        System.out.println(ans);
    }
}