解题思路
本题考查对区间贡献函数的上界分析与一次性观察，不必真的做区间 DP。
- 设全局最大值为 M=maxvi，全局最小值为 m=minvi。将整条序列作为一个子段时，贡献为H(1,n)=(M−m)×n
- 对任意合法划分，每一段 [L,R] 都有L≤i≤Rmaxvi−L≤i≤Rminvi≤M−m
因此该段贡献不超过 (M−m)×w(L,R)。把各段相加，总贡献不超过
题目内容
运维侧拿到一条长度为 n 的整型指标序列 v1,v2,…,vn，需要按连续子段做汇总评估。要求子段非空、首尾相接且覆盖整条序列，并使所有子段的「波动贡献」之和尽量大。对子段 vL,vL+1,…,vR，其长度为
w(L,R)=R−L+1
波动贡献定义为
H(L,R)=(max(vL,vL+1,…,vR)−min(vL,vL+1,…,vR))×w(L,R)
请给出可达到的最大总和。
输入描述
首先一行：序列长度 n (1≤n≤3×105)。
随后一行：n 个整型值构成的列表 v1,v2,…,vn (1≤vi≤109)。
输出描述
写出一个非负整型结果，表示该序列划分下能得到的最大总价值。
样例1
输入
3
2 5 1
输出
12
说明
将整段 [2,5,1] 作为一个子段：长度为 3，最大值为 5，最小值为 1，波动贡献为 (5−1)×3=12，即为最优总价值。
样例2
输入
4
1 5 2 4
输出
16
说明
将整段 [1,5,2,4] 作为一个子段：长度为 4，最大值为 5，最小值为 1，波动贡献为 (5−1)×4=16，即为最优总价值。
