反向子数组以在C ++中最大化数组值
因此,如果输入类似于[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