Background

数列分段（segment）

【题目描述】

给你一个长度为n（1≤n≤10​^6^​）的整数数列a​~1~​, a​~2~​, …, an（−10​^9^​≤ai≤10​^9^​）。你需要将这个数列分成若干段连续子序列，使得这些连续子序列的价值之和最大。

我们定义一个连续子序列的价值为：这个子序列中最大的数与最小的数之差。

【输入格式】

第一行包含一个整数n，表示数列的长度（1≤n≤10​^6^​）。

第二行包含n个整数，其中第i个整数表示数列中的第i个元素ai（−10​^9^​≤ai≤10​^9^​），相邻两数之间以一个空格分隔。

【输出格式】

一个整数，表示所有划分方案中，子序列价值之和的最大值。

【样例1输入】

5
1 2 3 1 2

【样例1输出】

3

【样例1解释】

一种最优划分方案是将该序列划分为2个子序列 [1 2 3] [1 2]，对应的子序列价值和为 (3−1)+(2−1)=3。

【样例2输入】

3
3 3 3

【样例2输出】

0

【样例2解释】

因为原序列中每个元素均为3，所以无论如何划分，每个子序列的价值均为0，对应的价值和也为0。

【样例3】

见选手目录下的segment/segment3.in与segment/segment3.ans（见CCF官方网站）。

【数据范围与提示】

对于20% 的数据，n≤100。

对于40% 的数据，n≤1000。

对于60% 的数据，n≤10000。

对于100% 的数据，1≤n≤10​^6^​，−10​^9^​≤ai≤10​^9^​。

提示

设 val(l,r) 表示从a~l~到ar 这段连续子序列对应的价值。

首先，若数列本身是单调递增（a​~1~​≤a​~2~​≤…≤an）或单调递减（a​~1~​≥a​~2~​≥…≥an）的，则不需要对其进行划分，其对应的价值之和为val(1,n)=|a​~1~​−an|，其中任意两对相邻元素ai和ai~+1~恰好贡献了 |ai−ai​~+1~​| 的价值，价值和可以表示为 |a​~1~​−a​~2~​|+|a​~2~​−a​~3~​|+…+|an−​~1~​−an|。此时，如果在ai和ai~+1~之间进行了划分，则将会损失 |ai−ai​~+1~​| 的价值。因此，对于本身就单调递增或者单调递减的数列，不需要进行划分就能够得到最大价值。

其次，我们分析数列中只存在一个极值（假设为ak）的情况，此时可能有如下两种不同的情况。

（1）a​~1~​≤a​~2~​≤…≤ak≥ak​~+1~​≥…≥an。

（2）a​~1~​≥a​~2~​≥…≥ak≤ak​~+1~​≤…≤an。

针对第一种情况（ak是极大值），我们可以得出如下结论。

（1）若不对这个数列进行划分，其对应的价值和为val(1,n)=max{|a​~1~​−ak|, |ak−a​~n~​|}。

（2）若在ak−~1~和ak之间进行划分，其对应的价值和为val(1,k−1)+val(k,n)=|a​~1~​−ak−​~1~​|+|ak−an|≥val(1,n)，而当i<k时，在ai−~1~和ai之间进行划分的价值和为val(1, i−1)+val(i, n)=|a​~1~​−ai−​~1~​|+|ak−an|≤val(1, k−1)+val(k, n)。

（3）若在ak和ak~+1~之间进行划分，其对应的价值和为val(1,k)+val(k+1,n)=|a​~1~​−ak|+|ak​~+1~​−an|≥val(1,n)，而当i>k时，在ai−~1~和ai之间进行划分的价值和为val(1, i−1)+val(i, n)=|a​~1~​- ak|+|ai−an|≤val(1,k)+val(k+1, n)。

因此此时的最优方案是选择在ak−~1~和ak之间进行一次划分，或者在ak和ak~+1~之间进行一次划分。

第二种情况（ak是极小值）的最优划分方案同第一种情况。

由更一般的分析可得，使价值和最大的划分方案中必然存在一种方案，使得划分出来的每一个连续子序列都是单调递增或者单调递减的。此时我们需要考虑的是，对于序列中存在的若干个极值（假设为ak），我们是在其与ak−~1~之间进行一次划分，还是在其与ak~+1~之间进行一次划分。

针对这个问题，我们可以使用动态规划算法求解，定义状态f~i~ 表示a~1~到a~i~ 这段连续子序列能够得到的最大价值和。

（1）若ai−​~2~​≤ai−​~1~​≤ai或ai−​~2~​≥ai−​~1~​≥ai，说明ai−~1~必然不是极值点，此时ai−~2~和ai−~1~之间及ai−~1~和ai之间都不会有划分，前i个数能够获得的最大价值和等于前i−1个数能够获得的最大价值和加上ai−~1~和ai 这一对数单独贡献的价值 |ai−​~1~​−ai|，即fi=fi−​~1~​+|ai−​~1~​−ai|；否则，说明ai−~1~是一个极值，此时需要在ai−~2~和ai−~1~之间或者在ai−~1~和ai之间进行一次划分。

（2）若在ai−~2~和ai−~1~之间进行一次划分，则fi=fi−​~2~​+|ai−​~1~​−ai|。

（3）若在ai−~1~和ai之间进行一次划分，则fi=fi−​~1~​。

即fi=max{ fi−​~2~​+|ai−​~1~​−ai|, fi−​~1~​}，最大价值和为fn。

Limitation

1s, 1024KiB for each test case.