题目描述

给定一个长度为 $N$ 的整数序列，请求出它的最大上升子序列和。

一个子序列需要保持原序列中的相对顺序。若子序列中的数满足：

$b_1 < b_2 < \cdots < b_k$

则称它为上升子序列。

注意：最大上升子序列和不一定来自最长的上升子序列。

例如序列：

100 1 2 3

最长上升子序列可以是：

1 2 3

它的和为 6；但最大上升子序列和为 100。

输入格式

第一行输入一个整数 $N$，表示序列长度。

第二行输入 $N$ 个整数，表示序列中的数。这些整数可能重复。

输出格式

输出一个整数，表示最大上升子序列和。

输入输出样例 #1

输入 #1

7
1 7 3 5 9 4 8

输出 #1

18

样例解释

对于序列：

1 7 3 5 9 4 8

最大上升子序列和为：

1 + 3 + 5 + 9 = 18

数据范围

$1 \le N \le 1000$

序列中的整数取值范围为 $0$ 到 $10000$。

提示

可以使用动态规划。

令 $dp[i]$ 表示以第 $i$ 个数结尾的最大上升子序列和。

若 $j < i$ 且 $a[j] < a[i]$，则可以用：

dp[i] = max(dp[i], dp[j] + a[i])

更新答案。