算法分析

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

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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) throws  IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        String[] s = reader.readLine().split(" ");
        for(int i = 1;i <= n;i++)
        {
            a[i] = Integer.parseInt(s[i - 1]);
        }
        for(int i = 1;i <= n;i++)
        {
            f[i] = a[i];//只有一个数时是1
            for(int j = 1;j < i;j++)
                if(a[j] < a[i])
                    f[i] = Math.max(f[i], f[j] + a[i]);
        }
        int res = 0;
        for(int i = 1;i <= n;i++)
            res = Math.max(res, f[i]);
        System.out.println(res);
    }
}