一本通-1285：最大上升子序列和（LIS变种）

【题目描述】 一个数的序列bi，当b1<b2<...<bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN)，我们可以得到一些上升的子序列(ai1,ai2,...,aiK)，这里1≤i1<i2<...<iK≤N。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中和最大为18，为子序列(1,3,5,9)的和。

你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。

【输入】 输入的第一行是序列的长度N(1≤N≤1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000(可能重复)。

【输出】 最大上升子序列和。

【输入样例】 7 1 7 3 5 9 4 8

【输出样例】 18

---

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> seq(1005);
vector<int> d(1005);

int LISsum()
{
    d[0] = seq[0];
    for (int i = 1; i < n; ++i) {
        d[i] = seq[i];
        for (int j = 0; j < i; ++j) {
            if (seq[j] < seq[i]) {
                d[i] = max(d[i], d[j] + seq[i]);
            }
        }
    }

    return *max_element(d.begin(), d.begin() + n);
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> seq[i];
    cout << LISsum() << endl;

    return 0;
}

其实就是LIS动态规划方法的稍微变动，用d[i]表示以seq[i]结尾的最大上升子序列和，状态转移方程是： $$ d[i] = \max(d[i], d[j] + seq[i]), 0 \leq j < i $$ 但是需要注意一点是，数组d[i]的元素应该初始化为seq[i]。假如还是初始化为0，考虑特殊情况：

4
-1 -2 -100 -3

不初始化输出结果会为0。