算法分析

扩展 最长上升子序列 求字典序问题

时间复杂度 $O(n^2)$

参考文献

算法基础课

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int[] a = new int[N];
    static int[] f = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 1;i <= n;i++) a[i] = scan.nextInt();
        int res = 0;
        for(int i = 1;i <= n;i++)
        {
            f[i] = 1;//只有一个数时是1
            for(int j = 1;j < i;j++)
                if(a[j] < a[i])
                    f[i] = Math.max(f[i], f[j] + 1);

            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }
}