5813: 【系列题】子序列(七)最大上升子序列和

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:3 Solved:2

Description

一个数的序列 b,当 b1<b2<...<b的时候,我们称这个序列是上升的。对于给定的一个序列( a1,a2,...,a),我们可以得到一些上升的子序列( 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 )。

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