C++で配列値を最大化するための逆サブアレイ

numsという整数配列が1つあるとします。この配列の値は、| nums [i] -nums [i +1]|の合計として定義されます。 0からn-1の範囲のすべてのiに対して。ここで、nは配列のサイズです。指定された配列の任意のサブ配列を選択して、それを逆にすることができます。この操作は1回しか実行できません。次に、最終的な配列の可能な最大値を見つける必要があります。

したがって、入力が[1,5,4,2,3]の場合、出力は10になります。

これを解決するには、次の手順に従います-

• ret：=0、extra：=0

• n：=numsのサイズ

• minVal：=inf、maxVal：=-inf

• 初期化i：=0の場合、i

  • 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 +エクストラの最大値と（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