最长上升子序列

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

来源：ACWing 算法基础课

题目描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤1000
−109≤数列中的数≤109

输入样例：

1
2
7
3 1 2 1 8 5 6

输出样例：

1
4

算法描述

本题数据范围较小，可以使用双层for循环+DP进行编写。

状态表示

f[i]表示以a[0]开始到a[i]的最大上升子序列的长度。

状态计算（集合划分）

判断是否上升

  1. 如果当前数a[i]大于其前面的数a[j],则说明两数符合上升规则
  2. 在符合上升规则时，再用dp[j]+1与当前的dp[i]的值作比较，不断更新dp[i]的值，再遍历完后顺利找到0 ~ i-1范围内的最大值，则值f[i]的值

笔者代码

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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[1010];
        int[] f = new int[1010];

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

        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);
    }
}