思路
定义 \(dp_i\) 表示将前 \(i\) 个分为若干段的价值总和。容易得到状态转移方程：
\[dp_i = \sum_{j = 1}^{i - 1}{dp_j \times (\max_{k = j + 1}^{i}\{a_k\} - \min_{k = j + 1}^{i}\{a_k\})}
\]
于是考虑将其拆成 \(\max_{k = j + 1}^{i}\{a_k\}\) 与 \(\min_{k = j + 1}^{i}\{a_k\}\) 两个子问题。
在这里我们先讨论 \(\max_{k = j + 1}^{i}\{a_k\}\) 这一子问题。
令 \(x\) 表示在 \(i\) 左边第一个大于 \(a_i\) 的位置。那么，一定有 \(\max_{k = x + 1}^{i}\{a_k\} = a_i\)；\(\max_{k = 1}^{x}\{a_k\} > a_i\)。
所以，\(a_i\) 能对答案产生贡献当且仅当 \(j > x\)。\(x\) 是很好求的，直接用单调栈维护即可。
那么我们现在的问题就变为了如何求 \(j \leq x\) 所能产生的贡献。
考虑用一个数组 \(mx_i\) 表示 \(\sum_{j = 1}^{i - 1}{dp_j \times \max_{k = j + 1}^{i}\{a_k\}}\)。
那么显然有：
\[mx_i = mx_x + (\sum_{k = x - 1})
\]