假设我们有一个称为nums的整数数组。此数组的值定义为| nums [i] -nums [i + 1] |的和。对于0到n-1范围内的所有i。其中n是数组的大小。我们可以选择给定数组的任何子数组并将其反转。我们只能执行一次此操作。然后,我们必须找到最终数组的最大可能值。
因此,如果输入类似于[1,5,4,2,3],则输出为10。
为了解决这个问题,我们将遵循以下步骤-
ret:= 0,额外:= 0
n:= nums的大小
minVal:= inf,maxVal:= -inf
对于初始化i:= 0,当i <n-1,更新(将i增加1)时,执行-
a:= nums [i],b:= nums [i + 1]
ret:= ret + | b-a |
extra:= Extra和|(nums [0]-b)-| a-b ||的最大值
extra:= Extra和|(nums [n-1]-a)-| a-b ||的最大值
maxVal:= maxVal的最大值以及a和b的最小值
minVal:= minVal的最小值以及a和b的最大值
返回ret + Extra和(maxVal-minVal)的最大值* 2
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class Solution { public: int maxValueAfterReverse(vector<int>& nums) { int ret = 0; int extra = 0; int n = nums.size(); int minVal = INT_MAX; int maxVal = INT_MIN; for(int i = 0; i < n - 1; i++){ int a = nums[i]; int b = nums[i + 1]; ret += abs(b - a); extra = max(extra, abs(nums[0] - b) - abs(a - b)); extra = max(extra, abs(nums[n - 1] - a) - abs(a - b)); maxVal = max(maxVal, min(a, b)); minVal = min(minVal, max(a, b)); } return ret + max(extra, (maxVal - minVal) * 2); } }; main(){ Solution ob; vector<int> v = {1,5,4,2,3}; cout << (ob.maxValueAfterReverse(v)); }
{1,5,4,2,3}
输出结果
10