解析
求一段最大上升子序列的和，我们假设现在已经遇到第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);
}
}
