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

  • Z时代
  • 2024-01-10
  • 分类：综合

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

以上是 反向子数组以在C ++中最大化数组值 的全部内容， 来源链接： utcz.com/z/322427.html

回到顶部