题解 | #最大上升子序列和#

#include <stdio.h>
//思路：注意当前子序列和一定是要与i之前所有满足上升条件的最大子序列和相加
//不仅仅是与上一个满足上升条件，是之前所有满足条件的最大值
int a[1000];//原始数组
int sum[1000];//序列和数组
void dp(int n) {
  sum[0] = a[0];
  for (int i = 1; i < n; i++) {
    int max = 0;
    for (int j = 0; j < i; j++) {
      if (a[j] < a[i] && sum[j] > max) {
        max = sum[j];
      }
    }
    sum[i] = max + a[i];
  }

}
int main() {
  int n;
  while (scanf("%d", &n) != EOF) {
    for (int i = 0; i < n; i++) {
      scanf("%d", &a[i]);
    }
    dp(n);
    int max = sum[0];
    for (int i = 1; i < n; i++) {
      if (sum[i] > max) {
        max = sum[i];
      }
    }
    printf("%d\n", max);
  }
}