当前位置：首页 > news >正文

企业网站源码简约门户网站备案

news 2025/10/10 13:18:04

企业网站源码简约,门户网站备案,河北省建设网站锁安装什么驱动,360收录提交入口网址作者推荐视频算法专题本文涉及知识点分类讨论解析几何 LeetCode1330. 翻转子数组得到最大的数组值给你一个整数数组 nums 。「数组值」定义为所有满足 0 < i < nums.length-1 的 |nums[i]-nums[i1]| 的和。你可以选择给定数组的任意子数组，并将该子…

作者推荐

视频算法专题

本文涉及知识点

分类讨论解析几何

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*10⁴
-10⁵ <= nums[i] <= 10⁵

分类讨论

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛