C++の配列arr[]でabs（i – j）* min（arr [i]、arr [j]）の最大値を検索します

この問題では、N個の整数値を要求する配列arr []が与えられます。私たちのタスクは、arrayarr []内のabs（i – j）* min（arr [i]、arr [j]）の最大値を見つけることです。

問題の説明 − 2つの要素の最小値の最大積値と、それらのインデックス間の絶対差を見つける必要があります。つまり、2つの値iとjの場合、最大化する必要があります。abs（i --j）* min（arr [i]、arr [j]）。

入力

arr[] = {5, 7, 3, 6, 4}

出力

16

説明

The maximum value is 16, between index 0 and 4
=> abs(0 - 4)*min(arr[0], arr[4])
=> 4*min(5, 4) => 4*4 = 16

ソリューションアプローチ

この問題の簡単な解決策は、ネストされたループを使用することです。 2つのループを取り、iとjの各ペアの値を計算します。そして、見つかったすべての値の最大値を返します。

このアプローチは優れていますが、O（n ² の次数の時間複合体があります。 。

この問題の効果的な解決策は、配列の最後からもう一方の先頭から2つのイテレータ値を使用することです。イテレータの値ごとに、必要な値を見つけて比較し、最大のinmaxVal変数を格納します。これは、両方のイテレータが互いに交差し、最後にmaxValを返すまで行います。

ソリューションの動作を説明するプログラム

例

#include<iostream>
using namespace std;
int calcMaxProdValue(int arr[], int n) {
   int maxVal = -100;
   int currentVal;
   int start = 0, end = n-1;
   while (start < end) {
      if (arr[start] < arr[end]) {
         currentVal = arr[start]*(end-start);
         start++;
      }
      else {
         currentVal = arr[end]*(end-start);
         end--;
      }
      maxVal = max(maxVal, currentVal);
   }
   return maxVal;
}
int main(){
   int arr[] = {5, 7, 3, 6, 4};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum value of abs(i – j) * min(arr[i], arr[j]) in an array is "<<calcMaxProdValue(arr,n);
   return 0;
}

出力

The maximum value of abs(i – j) * min(arr[i], arr[j]) in an array is 16