临沂建设中专官方网站,免费推广平台排行,关于数据机房建设的网站,广告在线制作图片SubmitStatisticProblem Description 一个只包含非负整数的序列bi#xff0c;当b1 b2 ... bS的时候#xff0c;我们称这个序列是上升的。对于给定的一个序列{a1, a2, ...,aN}#xff0c;我们可以得到一些上升的子序列{ai1, ai2, ..., aiK}#xff0c;这里1 …SubmitStatisticProblem Description 一个只包含非负整数的序列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}等等。这些子序列中序列和最大的是子序列{1, 3, 5, 9}它的所有元素的和为18。 对于给定的一个序列求出它的最大的上升子序列的和。 注意最长的上升子序列的和不一定是最大的哦。 Input 输入包含多组测试数据对于每组测试数据 输入数据的第一行为序列的长度 n(1 ≤ n ≤ 1000) 第二行为个非负整数 b1b2...bn(0 ≤ bi ≤ 1000)。 Output
对于每组测试数据输出其最大上升子序列的和。 Example Input 7
1 7 3 5 9 4 8 Example Output
18 #include stdio.h #include stdlib.h int main() { int n,sum[1001],k,j,i,a[1001],m,max; while(~scanf(%d,n)) { for(i1;in;i) scanf(%d,a[i]); sum[1]a[1]; for(i2;in;i) { m0; for(j1;ji;j) { if(a[j]a[i]msum[j]) msum[j]; } sum[i]ma[i];//上升子序列的和 } maxsum[1]; for(j2;jn;j) if(maxsum[j])//打擂台 maxsum[j]; printf(%d\n,max); } }
