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

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;cin>>n;
    int arr[n],dp[n];
    for(int i =0;i<n;i++)
        dp[i]=0;
    for(int i =0;i<n;i++)
        cin>>arr[i];
    dp[0] = arr[0];
    for(int i =1;i<n;i++){
        //找他之前的元素，找到比他小且dp最大的值
        int maxDp=-1;
        bool isFind=false;
        for(int j=0;j<i;j++)
            if(dp[j]>maxDp&&arr[j]<arr[i]){
                maxDp=dp[j];
                isFind=true;
            }   
        //加上该元素
        if(isFind)dp[i] = arr[i]+maxDp;
        else dp[i]=arr[i];
    }
    cout<<*max_element(dp,dp+n);
}
// 64 位输出请用 printf("%lld")

二重for循环，O(n^2)