本文涉及知识点
分类讨论 解析几何
LeetCode1330. 翻转子数组得到最大的数组值
给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。
你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作 一次 。
请你找到可行的最大 数组值 。
示例 1：
输入：nums = [2,3,1,5,4]
输出：10
解释：通过翻转子数组 [3,1,5] ，数组变成 [2,5,1,3,4] ，数组值为 10 。
示例 2：
输入：nums = [2,4,9,24,2,1,10]
输出：68
提示：
1 <= nums.length <= 3*104
-105 <= nums[i] <= 105
分类讨论
n = nums.length
一，不翻转。
二，翻转nums[0,i2)。i2 ∈ \in∈ [0,n)。没必要翻转两个数组。
三，翻转nums[i1,n)。i1 ∈ \in∈[0,n)。
四，翻转nums[i1,i2)，i1不为0,i2不为n,i1和i2是合法下标，i1<i2。nums[i1-1]和nums[i2]都会发生变化。
翻转之前：|a-b|+|c-d| 翻转之后：|a-c|+|b-d|。
翻转后的数组值变大 ⟺ \iff⟺ f(a,b,c,d) = |a-c|+|b-d| -|a-b|+|c-d| > 0。
令这4个数，下标从小大到大为a（nums[i1-1]）,b（nums[i1]）,c,d。
两点简化：
简化一，只需要考虑a <= c。
简化二，只需要考虑a <= b。
简化一证明
某组数a1,b1,c1,d1 ，a1 < c1 。
某外一组数{c1,d1,a1,b1} = f(c1,d1,a1,b1)=|c1-a1|+|d1-b1| - |c1-d1|-[a1-b1|
第一项第二项取反：|a1-c1|+|b1-d1|
第三项第四项互换：-|a1-b1|-|c1-d1|。
故：f(c1,d1,a1,b1) = f(a1,b1,c1,d1)
简化二证明：
某组数a1,b1,c1,d1 a1 > b1。
另外一组数{b1,a1,d1,c1} , f(b1,a1,d1,c1)=|b1-d1|+[a1-c1| -|b1-a1|-|d1-c1|
交换第一项和第二项目：|a1-c1|+|b1-d1|
第三项、第四项目，取反：-|a1-b1| - |c1,d1|
故：f(b1,a1,d1,c1) = f(a1,b1,c1,d1)。
等效问题
有一维四点a,b,c,d。 a <=b,a<=c。
线段ac的长度+线段bd的长度，能否大于线段ab的长度+线段cd的长度。
一，假定 b < c。
第一二种情况，两者有重合部分，长度不变。
第三四中情况，两者无重合部分，长度增加 两条线段的间隙× \times× 2
二,b > c。
全部变短或不变，全部部分重合或全部重合。
结论
a<b a<c ，两条线段有重叠部分，则变短或不变。 没有重叠部分，变长间隙长度× \times× 2。
上文已经证明了 两种简化的结果一样，现在来证明两个简化的判断条件一致。
简化一证明
某组数a1,b1,c1,d1 ，a1 < c1 。
简化前：线段a1b1和c1d1是否重叠。
简化后：线程c1d1和a1b1是否重叠。
两种显然等效。
简化二证明：
某组数a1,b1,c1,d1 a1 > b1。
线段a1b1就是b1a1,c1d1就是d1c1，所以无需证明。
重新简化
a<b 且b < c 且c<d。
ac的长度+bd的长度== ad的长度+bc的长度，都是ad的长度+bc的长度。
故调整a、b，使得a<b。调整c、d，使得c<d。
调整后增加的长度就是:(c-b)*2，结果为负数忽略。
代码
template<class ELE,class ELE2> void MinSelf(ELE* seft, const ELE2& other) { *seft = min(*seft,(ELE) other); } template<class ELE> void MaxSelf(ELE* seft, const ELE& other) { *seft = max(*seft, other); } #define MacEnumMask(mask,maskMax) for (int mask = maskMax; mask; mask = (mask - 1) & maskMax) class Solution { public: int maxValueAfterReverse(vector<int>& nums) { m_c = nums.size(); long long ans = 0; for (int i = 0; i + 1 < m_c; i++) { ans += abs(nums[i] - nums[i + 1]); } int iAdd = 0; for (int i = 1; i < m_c; i++) {//交换nums[i,m_c) MaxSelf(&iAdd, abs(nums.back() - nums[i - 1]) - abs(nums[i] - nums[i - 1])); } for (int i = 1; i < m_c; i++) {//交换nums[0,i) MaxSelf(&iAdd, abs(nums.front() - nums[i]) - abs(nums[i] - nums[i - 1])); } {//a,b在前 ,c,d在后 int b = max(nums[0], nums[1]); for (int j = 2; j < m_c; j++) { int c = min(nums[j - 1], nums[j]); int d = max(nums[j - 1], nums[j]); MaxSelf(&iAdd, 2 * c - 2 * b); MinSelf(&b, d); } } {//c,d在前 ,a,b在后 int b = max(nums[m_c-1], nums[m_c-2]); for (int j = m_c-2; j >0 ; j--) { int c = min(nums[j - 1], nums[j]); int d = max(nums[j - 1], nums[j]); MaxSelf(&iAdd, 2 * c - 2 * b); MinSelf(&b, d); } } return ans + iAdd; } int m_c; };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> nums; { Solution sln; nums = { 2,4,9,24,2,1,10 }; auto res = sln.maxValueAfterReverse(nums); Assert(68, res); } { Solution sln; nums = { 2, 3, 1, 5, 4 }; auto res = sln.maxValueAfterReverse(nums); Assert(10, res); } }
2023年5月
class Solution { public: int maxValueAfterReverse(vector& nums) { m_c = nums.size(); int iTotal = 0; for (int i = 0; i + 1 < m_c; i++) { iTotal += abs(nums[i] - nums[i + 1]); } //长度为1的子数组，结构不变。翻转整个数组结果不变 int iMaxAdd = 0; //处理以索引0开头或m_c-1结尾的子数组 for (int i = 0; i + 1 < m_c; i++) { //翻转[0,i] const int iLeft = abs(nums[i + 1] - nums[0]) - abs(nums[i + 1] - nums[i]); //翻转[i+1,m_c) const int iRight = abs(nums.back() - nums[i]) - abs(nums[i + 1] - nums[i]); iMaxAdd = max(iMaxAdd, iLeft); iMaxAdd = max(iMaxAdd, iRight); } int iMaxC = INT_MIN, iMinB = INT_MAX; for (int i = 0; i + 1 < m_c; i++) { const int& x = nums[i]; const int& y = nums[i + 1]; iMaxC = max(iMaxC, min(x, y)); iMinB = min(iMinB, max(x, y)); } iMaxAdd = max(iMaxAdd, 2 * (iMaxC - iMinB)); return iTotal + iMaxAdd; } int m_c; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
