闫式dp分析法

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1010;
int s[N] , q[N];
int n;
int main() {


    cin >> n;
    for (int i = 1 ; i <= n ; i ++ ) cin >> q[i];
    int res = 0;
    for (int i = 1 ; i <= n ; i ++ ) {
        s[i] = q[i];
        for (int j = 1 ; j < i ; j ++ )
            if (q[i] > q[j]) s[i] = max(s[i] , s[j] + q[i]); // 求f[i]
        res = max(s[i] , res);    
    }

    cout << res;
    return 0;
}