#include <iostream> #include <algorithm> #include <string> #include <cstdio> using namespace std; //最大上升子序列和 //区别于最长上升子序列,此时集合的属性为最大子序列和,即状态数组f[i]记录以a[i]结尾的 //最大上升子序列和 const int N = 1001; int n; int a[N], f[N]; int res() { //处理边界 if (n == 0)return 0; for (int i = 0; i < n; i++) f[i] = a[i];//初始化状态数组 int ma = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a[j] < a[i]) f[i] = max(f[i], f[j] + a[i]); } } for (int i = 0; i < n; i++) ma = max(ma, f[i]); return ma; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; cout << res() << endl; return 0; }