题目内容

小苯有一个长度为$n$的序列。他将$a$分为了$m$个不相交的连续段，每个段内的最大值构成了一个新的序列$b$。

现在小笨给定了你$n$序列，他希望最大化序列$b$的总和,请你帮他算一算$b$数组的总和最大可以达到多少吧

更正式的，小苯限定你可以将序列n划分为了$m$个区间

题解

题面描述

给定一个长度为 $n$ 的序列 $a$。你需要将该序列划分为 $m$ 个不相交的连续区间，记为 $[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$，其中必须满足对于任意 $j$ 满足 $r_j+1=l_{j+1}$。定义区间函数为
$f(l_j, r_j)$= max($a_{l_j}$,$a_{l_j+1}$,......,$a_{r_j}$) 得到的新序列为
$b = \{f(l_1, r_1),f(l_2, r_2),\ldots,f(l_m, r_m)\}$ 要求使得 $b_1+b_2+\ldots+b_m$ 最大化，求该最大值。