python

3.4 KiB

Raw Permalink Blame History Unescape Escape

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 1016. 最大上升子序列和

一、题目描述

一个数的序列 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)的和。

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

注意:最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。

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

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

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

数据范围 1≤N≤1000

输入样例：

7
1 7 3 5 9 4 8

输出样例：

二、题目分析

计算最长上升子序列长度的时候，我们定义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)`实现代码

#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)实现代码(树状数组版本)

题解传送门

五、关键字

魔改LIS
最大上升子序列和

3.4 KiB Raw Permalink Blame History Unescape Escape