| arr [i] – arr [j]-+ | i –j|の最大値C++で

この問題では、n個の整数の配列が与えられます。私たちのタスクは、| arr [i] -arr[j]|の最大値を見つけるプログラムを作成することです。 + |i-j|。

問題を理解するために例を見てみましょう

入力 −配列={4、1、2}

出力 − 4

説明 −

|arr[0] - arr[1]|+|0-1| = |4-1| + |-1| = 3+1 = 4
|arr[0] - arr[2]|+|0-2| = |4-2| + |-2| = 2+2 = 4
|arr[1] - arr[2 ]|+|1-2| = |1-2| + |1-2| = 1+1 = 2

この問題を解決するための簡単なアプローチは、ブルートフォースを使用することです。 2つのループを使用し、最大の差を見つけるアプローチ。

ただし、効率的なアプローチは、絶対関数のプロパティを使用することです。

方程式をデコードして解を見つけましょう

arr[i] - arr[j] + i - j = (arr[i] + i) - (arr[j] + j)
arr[i] - arr[j] - i + j = (arr[i] - i) - (arr[j] - j)
-arr[i] + arr[j] + i - j = -{(arr[i]-i) -(arr[j]-j)}
-arr[i] + arr[j] - i + j = -{(arr[i]+i) - (arr[j]+j)}

1番目と4番目は同じで、2番目と4番目は同じです。これを使用して、値arr[i]+-iを格納する2つの配列を作成します。

array1は、値arr [i] + i

array2は値を格納しますarr[i]-i

したがって、最大2つの値が見つかります

max（（max（array1）-min（array1））、（max（array2）-min（array2）））

例

ソリューションの実装を示すプログラム

#include<iostream>
using namespace std;
int maxDiff(int arr[], int n) {
   int ans = 0;
   for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
         ans = max(ans, abs(arr[i] - arr[j]) + abs(i - j));
   return ans;
}
int main() {
   int array[] = { 5, 7, 1, 2 };
   int n = sizeof(array) / sizeof(array[0]);
   cout<<"The maximum value of |arr[i] - arr[j]| + |i-j| is "<<maxDiff(array, n);
   return 0;
}

出力

The maximum value of |arr[i] - arr[j]| + |i-j| is 7