一个数的序列 $b_i$,当 $b_1<b_2<…<b_S$ 的时候,我们称这个序列是上升的。
对于给定的一个序列($a_1,a_2,…,a_N$),我们可以得到一些上升的子序列($a_{i_1},a_{i_2},…,a_{i_K}$),这里$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 \\le N \\le 1000$
输入样例:
7
1 7 3 5 9 4 8
输出样例:
18
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(动态规划) $O(n^2)$
与 最长上升子序列 类似,我们改一下状态转移方程即可。
需要注意我们这里求的是和,而不是像 最长上升子序列 一样的长度。
修改状态表示为 $f[i]$ 表示从 $1$ 到 $i$的最长上升子序列和。
首先我们初始化 $f[i]$ 为$a[i]$。
计算时为 $f[i] = max(f[i],f[i] + a[j])$,累计 $a[j]$ 的和。
最终遍历 $1$ 到 $n$ ,取$max$,输出$res$即可。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N];
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
for(int i = 1;i <= n;i ++){
f[i] = a[i];
for(int j = 1;j < i;j ++){
if(a[i] > a[j]) f[i] = max(f[i],f[j] + a[i]);
}
}
int res = 0;
for(int i = 1;i <= n;i ++) res = max(res,f[i]);
printf("%d\n",res);
return 0;
}