单点时限: 2.0 sec
内存限制: 256 MB
由非负整数 $b_i(0 \leqslant i \lt m-1) $ 满足 $(i \lt j, b_i < b_j)$时被称为长度为 $m$ 的上升序列。
一个长度为 $n$ 的序列 $a_0, a_1, …,a_{n-1}$,存在多种上升子序列:
$a_{i_0}, a_{i_1}, …, a_{i_k} (0 \leqslant i_0 \lt i_1\lt…\lt i_k \lt n)。$
例如:序列 1, 7, 3, 5, 9, 4, 8 的上升子序列有 (1, 7)、(3, 5, 8)、(1, 3, 5, 9) 等。这些上升子序列中序列和最大为 18,为上升子序列 1, 3, 5, 9 的和。
对于给定的序列,求出上升子序列和的最大值。
第 1 行:整数 $T$ ($1 \le T \le 10$) 为问题数
第 2 行:第 1 个问题的整数 $n (1 \leqslant n \leqslant 5000)$
第 3 行:n 个整数$ a_i (0 \leqslant a_i \leqslant 4000)$, 由一个空格隔开。这些数的值有些可能是相等的。
后面是第 2 ∽ T 个问题的数据。格式与第 1 个问题相同。
对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0:
等),然后在一行中输出上升子序列和的最大值。
2 7 1 7 3 5 9 4 8 4 100 20 20 3
case #0: 18 case #1: 100