python/TangDou/AcWing/LIS/1016.md

##[$AcWing$ $1016$. 最大上升子序列和](https://www.acwing.com/problem/content/1018/)

### 一、题目描述
一个数的序列 $b_i$，当 $b_1<b_2<…<b_S$ 的时候，我们称这个序列是上升的。

对于给定的一个序列($a_1,a_2,…,a_N$)，我们可以得到一些上升的子序列($a_{i1},a_{i2},…,a_{iK}$)，这里$1≤i_1<i_2<…<i_K≤N$。

比如，对于序列$(1,7,3,5,9,4,8)$，有它的一些上升子序列，如$(1,7),(3,4,8)$等等。

这些子序列中和最大为$18$，为子序列$(1,3,5,9)$的和。

你的任务，就是对于给定的序列，**求出最大上升子序列和**。

<font color='red' size=4><b>注意:最长的上升子序列的和不一定是最大的</b></font>，比如序列$(100,1,2,3)$的最大上升子序列和为$100$，而最长上升子序列为$(1,2,3)$。

**输入格式**
输入的第一行是序列的长度$N$。

第二行给出序列中的$N$个整数，这些整数的取值范围都在$0$到$10000$(可能重复)。

**输出格式**
输出一个整数，表示最大上升子序列和。

**数据范围**
$1≤N≤1000$

**输入样例**：
```cpp {.line-numbers}
7
1 7 3 5 9 4 8
```

**输出样例**：
```cpp {.line-numbers}
18
```


### 二、题目分析
计算最长上升子序列长度的时候，我们定义$f[i]$为以第$i$个元素结尾的最长子序列的长度，并且采用双重循环的方法，固定每一个数字$A$时，向前查找可以衔接到哪个数字$B_i$后面,如果$A>B_i$,则尝试接在$B_i$后面，可以获取到一个可能的最长子序列长度$L_i$,所有的$L_i$　$PK$一下$MAX$,就是答案。

本题不再要求计算$LIS$的最长长度，而是计算总和，和上面的思考方式一样，但状态表示有了变化：
#### 状态表示
$f[i]$:以第$i$个元素结尾的最大子序列和

也采用双重循环的方法，固定每一个数字$A$时，向前查找可以衔接到哪个数字$B_i$后面,如果$A>B_i$,则尝试接在$B_i$后面，可以获取到一个可能的最大子序列和$S_i$,所有的$S_i$　$PK$一下$MAX$,就是答案。

综上所述，此题与$LIS$还是有区别的，并不是$LIS$的扩展，而是$LIS$问题的变形，不是在求解$LIS$问题基础上再增加点什么就能解决，而是采用了类似的思路。$LIS$问题有三种解法:

* **朴素版动态规划**　 可以继承思想，变形解决
* **贪心+二分**　已经无效，不能继承，思路不同
* **树状数组**　　

### 三、$O(n^2)$实现代码

```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

// 最大上升子序列和
int n;
const int N = 100010;
int a[N];
int f[N];//以第i个元素结尾的最大子序列和
int res;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        f[i] = a[i]; // 最大上升子序列（个数）这里是1,此处是a[i]
        for (int j = 1; j < i; j++)
            // 最大上升子序列（个数）这里是加1,此处是+a[i]
            if (a[i] > a[j]) f[i] = max(f[i], f[j] + a[i]);
        res = max(res, f[i]);
    }
    printf("%d ", res);
    return 0;
}
```


###　四、$O(nlogn)$实现代码(树状数组版本)

**[题解传送门](https://www.cnblogs.com/littlehb/p/17510484.html)**

### 五、关键字
- 魔改$LIS$
- 最大上升子序列和