最长上升子序列和

题目 最大上升子序列和

思路分析

求出最大上升子序列的最大和

注意，单独一个数也是一个最大上升子序列，如比如序列 (100,1,2,3) 的最大上升子序列和为 100 ，而最长上升子序列为 (1,2,3)

其实只需要将 最长上升子序列中集合的属性从Num更改为Max即可

状态表示 fi: 考虑前i个元素，以第i个元素结尾的最大上升子序列的方案

状态属性: 最大上升子序列和最大 Max

状态转移:

集合划分:

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int w[N];

int f[N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>w[i];

    for(int i=1;i<=n;i++){

        f[i]=w[i];

        for(int j=0;j<i;j++){

            if(w[j]<w[i])

              f[i]=max(f[i],f[j]+w[i]);

        }

    }

    int res=0;

    for(int i=1;i<=n;i++)

        res=max(res,f[i]);

    cout<<res;

    return 0;

}

同类题型

视频讲解

⬅️ 最长上升子序列2 🏠 00-刷题理模型 ➡️ 最长上升子序列模型练习