题目描述

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

思路

此处要分析动态规划中的状态表示，f[i]的意义是以第i个为结尾的上升子序列，而我们需要求的属性是MAX，对于f[i]我们可以划分为 以i之前一个数为结尾的上升子序列 + 1，此处需满足条件是a[i] > a[j].
最后需要遍历所有f，来存一个最大值

时间复杂度分析

根据动态规划的时间复杂度为 状态数量 ✖️ 转移数量（我理解为转移方程的操作规模）
即为 $O(n^2)$

JAVA 代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = 1100;
        int[] f = new int[N];
        int[] a = new int[N];

        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;//每一个f[i]的初始化都是1，因为最短就是本身，即为1；
            for (int j = 1; j < i; j++) {
                if (a[i] > a[j]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }

        int res = 0; //通过遍历f数组，来求最大值

        for (int i = 1; i <= n; i++) {
            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }
}