反向子数组以在C ++中最大化数组值

假设我们有一个称为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