---
title: "最长上升子序列和"
created: 2025-11-28
tags:
  - 算法
---

# 最长上升子序列和

## 题目 最大上升子序列和

![[image-f5cf6129.png]]

![[image-f095e952.png]]

## 思路分析

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

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

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

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

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

状态转移:

![[image-c565ef07.png]]

集合划分:

![[image-92073073.png]]

## 代码实现

```cpp
#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|最长上升子序列2]] 🏠 [[00-刷题理模型]] ➡️ [[最长上升子序列模型练习|最长上升子序列模型练习]]