//转移方程:ans[i] = max(a[i], ans[j] + a[i]) j < i && a[j] < a[i] #include <iostream> #include <cstring> #include <algorithm> #include <string> using namespace std; int ans[1010]; int a[1010]; int n; int main() { //freopen("1.txt", "r", stdin); while(cin >> n && n != 0) { for(int i = 1; i <= n; i++) { cin >> a[i]; ans[i] = a[i]; for(int j = 1; j < i; j++) { if(a[j] < a[i]) ans[i] = max(ans[i], ans[j] + a[i]); } } int _max = ans[1]; for(int i = 2; i <= n; i++) if(ans[i] > _max) _max = ans[i]; cout << _max << endl; } return 0; }
