程序在C ++中单次反转后查找最大相邻绝对值总和
假设我们有一个称为nums的数字列表,并且我们最多可以反转一次列表中的任何子列表。执行完此操作后,我们必须找到最大可能值
$\displaystyle\sum\limits_{i=0}^{n-2}|nums[i+1]-[nums[i]|$
因此,如果输入类似于nums=[2,4,6],则输出将为6,因为当我们反转[4,6]时,我们将得到列表为[2,6,4],并且值|2−6|+|6−4|=6
为了解决这个问题,我们将遵循以下步骤-
如果nums的大小<=1,则-
返回0
回答:=0
n:=nums的大小
对于初始化i:=1,当i<n时,更新(将i增加1),-
ans:=ans+|nums[i]−nums[i−1]|
orig:=ans
对于初始化i:=1,当i<n−1,更新(i增加1)时,-
ans:=ans和orig的最大值-|(nums[i]-nums[i+1]|+|nums[0]-nums[i+1]|
ans:=ans和orig的最大值-|(nums[i]-nums[i-1]|+|nums[n-1]-nums[i-1]|
pp:=-|nums[1]-nums[0]|
pm:=-|nums[1]-nums[0]|
mp:=-|nums[1]-nums[0]|
mm:=-|nums[1]-nums[0]|
对于初始化j:=2,当j<n−1,更新(j增加1)时,-
jerror:=|nums[j+1]−nums[j]|
ans:=ans和(orig+pp-jerror-nums[j]-nums[j+1])的最大值
ans:=ans和((orig+pm-jerror-nums[j]+nums[j+1])的最大值
ans:=ans和((orig+mp−jerror+nums[j]−nums[j+1])的最大值
ans:=ans和(orig+mm−jerror+nums[j]+nums[j+1])的最大值
pp:=pp和-|nums[j]-nums[j-1]|的最大值
pm:=pm和-|nums[j]-nums[j-1]|的最大值
mp:=mp和-|nums[j]-nums[j-1]|的最大值
mm:=mm和-|nums[j]-nums[j-1]|的最大值
返回ans
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h> using namespace std; int solve(vector<int>& nums) { if (nums.size() <= 1) return 0; int ans = 0; int n = nums.size(); for (int i = 1; i < n; i++) { ans += abs(nums[i] − nums[i − 1]); } int orig = ans; for (int i = 1; i < n − 1; i++) { ans = max(ans, orig − abs(nums[i] − nums[i + 1]) + abs(nums[0] − nums[i + 1])); ans = max(ans, orig − abs(nums[i] − nums[i − 1]) + abs(nums[n − 1] − nums[i − 1])); } int pp = −abs(nums[1] − nums[0]) + nums[0] + nums[1]; int pm = −abs(nums[1] − nums[0]) + nums[0] − nums[1]; int mp = −abs(nums[1] − nums[0]) − nums[0] + nums[1]; int mm = −abs(nums[1] − nums[0]) − nums[0] − nums[1]; for (int j = 2; j < n − 1; j++) { int jerror = abs(nums[j + 1] − nums[j]); ans = max(ans, orig + pp − jerror − nums[j] − nums[j + 1]); ans = max(ans, orig + pm − jerror − nums[j] + nums[j + 1]); ans = max(ans, orig + mp − jerror + nums[j] − nums[j + 1]); ans = max(ans, orig + mm − jerror + nums[j] + nums[j + 1]); pp = max(pp, −abs(nums[j] − nums[j − 1]) + nums[j − 1] + nums[j]); pm = max(pm, −abs(nums[j] − nums[j − 1]) + nums[j − 1] − nums[j]); mp = max(mp, −abs(nums[j] − nums[j − 1]) − nums[j − 1] + nums[j]); mm = max(mm, −abs(nums[j] − nums[j − 1]) − nums[j − 1] − nums[j]); } return ans; } int main(){ vector<int> v = {2, 4, 6}; cout << solve(v); }
输入值
{2, 4, 6}输出结果
6