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)