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

#include <ios>
#include <iostream>
#include <cstring>


using namespace std;

const int N = 1010;

int a[N];
int dp[N];

int main() {


    int n;
    while (cin >> n) {
        int ans = 0;
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++) {
            dp[i] = a[i];
            int j;

            for (j = i - 1; j > 0; j--) {
                if (a[j] < a[i]) {
                    dp[i] = max(dp[j] + a[i], dp[i]);
                }
            }


            ans = max(ans, dp[i]);
        }
        cout << ans << endl;

    }



    return 0;
}