1330. 翻转子数组得到最大的数组值
关键词：数学、分类讨论
题目来源：1330. 翻转子数组得到最大的数组值 - 力扣（Leetcode）
题目描述
T数学给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。
你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作 一次 。
请你找到可行的最大 数组值 。
输入：nums = [2,3,1,5,4]
输出：10
解释：通过翻转子数组 [3,1,5] ，数组变成 [2,5,1,3,4] ，数组值为 10 。输入：nums = [2,4,9,24,2,1,10]
输出：68数据范围
1 <= nums.length <= 3*10^4
-10^5 <= nums[i] <= 10^5问题分析
设翻转的点为i和j，不难发现，翻转整个数组或者翻转单个元素并不影响数组值，故只考虑i＜j的情况。
设i-1处为A，i处为B，j处为C，j+1处为D。
先考虑边界，即i=0或者j＝n-1的情况，此时A或D不存在，那么翻转后的数组值可通过两遍扫描得到。
当A、B、C、D均存在时，有如下等式成立，
v = 翻转后的值 - 翻转前的值 = ( |A-C| + |B-D| ) - ( |A-B| + |C-D| )我们的目标就是使得v尽可能大，直接枚举A、B、C、D是不太行的，复杂度较高，所以需要进一步分类讨论，排除某些情况，分类讨论肯定围绕去绝对值进行（以下不考虑相等的情况，相等的情况放到大于或小于都可以）。
当A＞C且B＞D时
- 若A＞B且C＞D时，v = 2B-2C；
- 若A＞B且C＜D时，v = 2B-2D；
- 若A＜B且C＞D时，v = 2A-2C；
- 若A＜B且C＜D时，v = 2A-2D；
发现，AB取小，CD取大
当A＞C且B＜D时
- 若A＞B且C＞D时，v = 2D-2C，小于0，排除；
- 若A＞B且C＜D时，v = 0，排除；
- 若A＜B且C＞D时，v = 2A-2B + 2D-2C，小于0，排除；
- 若A＜B且C＜D时，v = 2A-2B，小于0，排除；
注意前提条件i＜j，也即AB在CD前面
讨论到这其实不用往下讨论了，原因在于：翻转整个数组并不影响数组值，所以CD可看做将整个数组翻转后的AB，AB和CD在效果上是对称的。
所以后两种情况A＜C且B＞D、当A＜C且B＜D与上面讨论的两种情况其实是对称的，只需要将前两种情况得到的做法再作用于完全翻转后的数组，将正反两个答案进行比较，即可得到最终答案。
先考虑“正”的答案，经过前面讨论可知，需要做的就是找到AB较小值的最大值和CD较大值的最小值。
再考虑“反”的答案，由于AB和CD对称，所以，只需要找到CD较小值的最大值和AB较大值的最小值。
再次提醒，以上讨论，AB均在CD前面。
观察正反两个答案，最终结果就是相邻两数较小值的最大值和相邻两数较大值的最小值的差，这通过一遍扫描就可以得到。
综上，处理边界扫描两遍，处理一般情况扫描一遍，三遍扫描解决此题。
代码实现
int maxValueAfterReverse(vector<int> &nums) {
int n = nums.size(), d = 0;
if (n < 3)return d;
int v = 0;
for (int i = 1; i < n; i++)
v += abs(nums[i] - nums[i - 1]);
// i=0
for (int i = 2; i < n; i++)
d = max(abs(nums[i] - nums[0]) - abs(nums[i] - nums[i - 1]), d);
// j=n-1
for (int j = n - 3; ~j; j--)
d = max(abs(nums[j] - nums[n - 1]) - abs(nums[j] - nums[j + 1]), d);
// 一般情况
int mi = min(nums[0], nums[1]);
int ma = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
mi = max(min(nums[i], nums[i - 1]), mi);
ma = min(max(nums[i], nums[i - 1]), ma);
}
return v + max((mi - ma) * 2, d);
}时间复杂度：O(n)
空间复杂度：O(1)