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

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;cin >> n;
    int arr[n];
    int dp[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        dp[i] = arr[i];
    }
    int maybe=0;
    for (int i = 1; i < n; i++) {
        for (int j = i-1; j>=0; j--) {
            //如果前面的元素小于后面的，则构成上升序列
            if ((arr[j] < arr[i]) && (dp[j]>maybe)) {
                maybe=dp[j];
            }
        }
        dp[i]+=maybe;
        maybe = 0;
    }
    cout << *max_element(dp, dp + n);
}

和王道不一样的思路