解析

求一段最大上升子序列的和，我们假设现在已经遇到第i个数了，那么从第0个数到第i个数之间的最大上升子序列和一定是第0-i之间的某个小于第i个数的最大子序列和加上第i个数，这个地方可能有点绕，拿示例来说明下：

i	1	2	3	4	5	6	7
a[i]	1	7	3	5	9	4	8

从第1个数到第4个数，即（1,7,3,5）这个序列中的最大上升子序列的和一定是某个小于第4个数（也就是5）的某个数（可能是1或者3）的序列（即（1）序列或者（1,3）序列）的和加上5。

因此只需要找出i之前的小于第i个的数的子序列的和并求出期间的最大值就可以了，因此，我们假设一个opt数组，opt[i]表示的是从第1个数到第i个数之间的最大子序列的和，所以opt[i]=max{opt[0],~,opt[i]},最后只要求出opt[]数组中的最大值即可。

代码

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[n + 1];
        int[] opt = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            a[i] = scanner.nextInt();
            opt[i] = a[i];
        }
        for (int i = 1; i < n + 1; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (a[i] > a[j]) {
                    int A = opt[j] + a[i];
                    int B = opt[i];
                    opt[i] = Math.max(A, B);
                }
            }
        }
        int max = 0;
        for (int x : opt) {
            if (x > max)
                max = x;
        }
        System.out.println(max);
    }
}