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

【C++ 数学】1330. 翻转子数组得到最大的数组值|2481

news 2024/11/6 8:09:20

本文涉及知识点

数学
类似曼哈顿距离的证明过程

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
提示：
2 <= nums.length <= 3*10⁴
-10⁵ <= nums[i] <= 10⁵
答案保证在 32 位整数范围内。

数学

翻转子数组nums[i…j]后，只有翻转子数组和未翻转的部分的交界处，会发生变化。
一，翻转[0…n-1]结果不变。其数组值为ans。
二，翻转[0…j]，j < n-1 ，|nums[j+1]-nums[0]|-|nums[j+1]-nums[j]|。时间复杂度：O(n)。
三，翻转[i…n-1],i >0 ，|nums.back()-nums[i-1]|-|nums[i]-nums[i-1]|。时间复]杂度：O(n)。
四，翻转[i…j]，i > 0 且 j < n-1,i < j。暴力处理时间复杂度是：O(nn)。
我们令a = nums[i-1],b=nums[i],c=nums[j],d=nums[j+1]。
求e=|a-c|+|b-d|
f= e- |a-b|-|c-d|。
令二三四的最大值是iMax，iMax = max(iMax,0)。
答案是：ans + iMax。
显然e最大的时候f也最大。
$e=max\begin{cases} a-c+b-d \\ c-a+b-d\\ a-c+d-b\\ c-a+d-b\\ \end{cases}\rightarrow max\begin{cases} a+b-(c+d)\\ -(a-b)+c-d \\ (a-b)-(c-d)\\ -(a+b)+c+d\\ \end{cases}$
pre[0]记录a+b-|a-b|的最大值
pre[1]记录a-b-|a-b|的最大值
pre[2]记录-a-b-|a-b|的最大值
pre[3]记录-a+b-|a-b|的最大值
cur[0…3]记录对应的c和d。
结束后 pre = cur。
curMax = max(pre[0]+cur[2],pre[1]+cur[3],pre[2]+cur[0],pre[3]+cur[1])

代码

核心代码

class Solution {public:int maxValueAfterReverse(vector<int>& nums) {const int N = nums.size();int ans = 0, iMax = 0;for (int i = 1; i < N; i++) {ans += abs(nums[i] - nums[i - 1]);iMax = max(iMax, abs(nums[i] - nums[0]) - abs(nums[i] - nums[i - 1]));//翻转[0,i-1]iMax = max(iMax, abs(nums.back() - nums[i - 1]) - abs(nums[i] - nums[i - 1]));//翻转[i,N-1]}const int iNotMay = INT_MIN / 2;int iPreMax[4] = { iNotMay,iNotMay,iNotMay,iNotMay };for (int i = 1; i < N; i++) {const int& c = nums[i - 1], d = nums[i],e = abs(c-d);int cur[4] = {c+d-e,c-d-e,-c-d-e,-c+d-e};for (int j = 0; j < 4; j++) {iMax = max(iMax, iPreMax[j] + cur[(j + 2) % 4]);}for (int j = 0; j < 4; j++) {iPreMax[j] = max(iPreMax[j], cur[j]);}}return ans + iMax;}};

单元测试

vector<int> nums;TEST_METHOD(TestMethod1){nums = { 1,2,3 };auto res = Solution().maxValueAfterReverse(nums);AssertEx(3, res);}TEST_METHOD(TestMethod2){nums = { 1,4,3,5 };auto res = Solution().maxValueAfterReverse(nums);AssertEx(8, res);}TEST_METHOD(TestMethod11){nums = { 2, 3, 1, 5, 4 };auto res = Solution().maxValueAfterReverse(nums);AssertEx(10, res);}TEST_METHOD(TestMethod12){nums = { 2,4,9,24,2,1,10 };auto res = Solution().maxValueAfterReverse(nums);AssertEx(68, res);}TEST_METHOD(TestMethod13){nums = { 2,5,1,3,4 };auto res = Solution().maxValueAfterReverse(nums);AssertEx(11, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功