【题目大意】
给定一个数组，让你去求最大的 / 上升 / 子序列 / 之和，是一道经典的 dp（动态规划）题。
【样例解读】
上升子序列有：1 7，3 4 8，1 3 5 9，1，7，3，5，9，4，8。
它们的和分别为：8，15，18，1，7，3，5，9，4，8。
显然，最大的为 181818，答案就是 181818。需要注意的是，每个元素都可以作为一个上升子序列。
【思路分析】
既然是一道 dp，那么我们需要：
1. 终止条件\color{red}{\texttt{终止条件}}终止条件：其实就是每个元素都可以作为一个上升子序列。
2. 状态转移方程\color{red}{\texttt{状态转移方程}}状态转移方程：现在假设有元素下标 iii 和比他小的元素下标 jjj，我们是不是可以用 dpkdp_kdpk 来存储以第 kkk 个元素结尾的最大上升子序列和呢？如果下标 iii 对应的元素比 jjj 对应的元素大，那么 aia_iai 就可以接在以 aja_jaj 结尾的上升子序列后面，成为新的结尾，就用 dpidp_idpi 存储。于是乎，可以判断当前以第 iii 个元素结尾的最大上升子序列和与 aia_iai 加入 dpjdp_jdpj 的最大上升子序列和谁大，从而改变 dpidp_idpi ，就有了 dp[i]
= max(dp[i], a[i] + dp[j])。
是不是答案一下子就出来了？
【代码分析】
结合以上三个板块，代码可以分 444 个步骤解决:
1. 定义状态：我们使用一个数组 dpdpdp，其中 dpidp_idpi 表示以第 iii 个元素结尾的最大上升子序列和。例如，如果序列是 [1,7,3,5,9,4,8][1, 7, 3, 5, 9, 4, 8][1,7,3,5,9,4,8]，那么 dp5dp_5dp5 表示以 999 结尾的最大上升子序列和。
2. 初始化：每个元素本身都可以作为一个长度为 111 的上升子序列，所以：
3. 状态转移：对于每个 iii，我们遍历它前面的所有元素 j(j<i)j(j<i)j(j<i)，如果 ai>aja_i>a_jai >aj ，说明可以将 aia_iai 接在以 aja_jaj 结尾的上升子序列后面：
这样，我们就可以不断更新 dpidp_idpi ，使其保持为以 aia_iai 结尾的最大上升子序列和。
然后再在 dpdpdp 数组中找最大值，即为所求的最大上升子序列和。
4. 输出答案：将答案输出。
【PS】：如果你想要高大上的代码，你可以将 aaa 数组清空为 kkk 的代码写为：memset(数组名（a）, 要清空成为的数（k）, sizeof(数组名（a）));。比如：memset(array, 0, sizeof(a));。
AC CODE（有注释）
算法复杂度：O(n2)O(n^2)O(n2)。
AC CODE（无注释）
测试正确证明📝
如有错误，请各位大佬指出，🦀🦀。
