上升子序列的最大和！长度不一定最长

总时间限制:1000ms内存限制:65536kB描述一个数的序列bi，当b1b2bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,

总时间限制:

1000ms

内存限制:

65536kB

描述

一个数的序列bi，当b1

输入

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

输出

最大上升子序列和

样例输入

71 7 3 5 9 4 8

样例输出

18

注意！！！是求上升子序列的最大值（长度不一定最长，但值一定最大）

#include using namespace std; int main() { int i,j,n,max,k; int a[1005],dp[1005]; //dp[i]存储当前的最长上升子序列的和的最大值 scanf("%d", for(i=0;ia[j]} } max=-1; for(i=0;imax) //寻找最大值 { max=dp[i]; } printf("%d\n",max); return 0; } 如果求长度最长的子序列的和（如果长度相同，输出第一个） 可参考一下代码#include #include using namespace std; int main() { int i,j,n,max,k; int a[1005],b[1005],c[1005]; //b[i]存储当前的最长上升子序列的值 scanf("%d", for(i=0;ia[j] c[i]=c[j]+a[i]; } } max=0; for(i=0;imax) //寻找最大值 { max=b[i]; k=i;} printf("%d\n",c[k]); return 0; }