暂无测试数据。
题目描述
一个数的序列 bi,当 b1<b2<⋯<bS 的时候,我们称这个序列是上升的。
对于给定的一个序列 {aN},我们可以得到一些上升的子序列 {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},和仅为 6。
输入格式
输入的第一行是原序列的长度 N。
第二行给出原序列中的 N 个整数,第 i 个整数为 ai。
输出格式
输出一个整数,表示最大上升子序列和。
样例 #1
样例输入 #1
样例输出 #1
提示
【数据范围】
对于 20% 的数据,N≤20。
对于 100% 的数据,1≤N≤103。