5813: 【系列题】子序列(七)最大上升子序列和
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:3
Solved:2
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 )等等。这些子序列中和最大为 18 ,为子序列( 1,3,5,9 )的和。
你的任务,就是对于给定的序列,求出最大上升子序列和。注意,最长的上升子序列的和不一定是最大的,比如序列( 100,1,2,3 )的最大上升子序列和为 100 ,而最长上升子序列为( 1,2,3 )。
你的任务,就是对于给定的序列,求出最大上升子序列和。注意,最长的上升子序列的和不一定是最大的,比如序列( 100,1,2,3 )的最大上升子序列和为 100 ,而最长上升子序列为( 1,2,3 )。
Input
输入的第一行是序列的长度N。第二行给出序列中的N个整数a1~aN,
Output
最大上升子序列和。
Sample Input Copy
7
1 7 3 5 9 4 8
Sample Output Copy
18
HINT
样例说明:
对于数组[1, 7, 3, 5, 9, 4, 8],和最大的子序列是(1, 3, 5, 9),和为18
数据范围:
1<=N<=1000
0<=ai<=10000