C ++で許可されている特定の配列での回転のみでSum（i * arr [i]）の最大値を検索します

この問題では、n個の要素で構成される配列arr[]が与えられます。特定の配列での回転のみが許可されているSum（i * arr [i]）の最大値を見つける必要があります。 （i * arr [i]）の最大合計を見つけるために、任意の数の回転を実行できます。

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

入力

arr[] = {4, 1, 3, 7, 2}

出力

43

説明

配列を1回回転させて最大値を取得します。回転後、配列は{2、4、1、3、7}

合計=0* 2 + 1 * 4 + 2 * 1 + 3 * 3 + 4 * 7 =0 + 4 + 2 + 9 + 28 =43

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

この問題の簡単な解決策は、アレイをn回回転させることです。各回転の後、sum（i * arr [i]）を見つけて、すべての値の最大値を返します。これは素晴らしいことですが、時間計算量はO（n2）のオーダーです。この問題のより効率的な解決策は、数式を使用して回転せずにsum（i * arr [i]）の値を見つけることです。

数式を数学的に導きましょう

Let the sum after k rotation is equal to sum(k).
sum(0) = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] => eq 1

次に、値をローテーションします。その後、合計は次のようになります。

sum(1) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] => eq 2 Subtracting eq2 - eq 1
sum(1) - sum(0) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] - 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1]
sum(1) - sum(0) = arr[0] + arr[1] + … arr[n-2 ] - (n - 1)*arr[n-1]

同様に、sum（2）-sum（1）、

sum(2) - sum(1) = arr[0] + arr[1] + …. arr[n - 3] - (n - 1)*arr[n-2] + arr[n-1]

方程式を一般化する、

sum(k) - sum(k-1) = arr[0] + arr[1] + …. Arr[n - 1] - (n)*arr[n - k]

これを使用して、sum（0）を使用してsum（k）の値を見つけることができます

ここで、ソリューションでは、配列のすべての値の合計を見つけてから、sum（0）の値を見つけます。ループを使用して、1からnまでのsum（k）のすべての値を見つけます。そして、それらの最大値を返します。

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

例

#include <iostream>
using namespace std;
int findMaxSumRotation(int arr[], int n){
   int arrSum = 0;
   int currSum = 0;
   for (int i=0; i<n; i++){
      arrSum = arrSum + arr[i];
      currSum = currSum+(i*arr[i]);
   }
   int maxSum = currSum;
   for (int j=1; j<n; j++){
      currSum = currSum + arrSum-n*arr[n-j];
      if (currSum > maxSum)
         maxSum = currSum;
   }
   return maxSum;
}
int main(){
   int arr[] = {4, 1, 3, 7, 2};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum value of sum(i*arr[i]) using rotations is "<<findMaxSumRotation(arr, n);
   return 0;
}

出力

The maximum value of sum(i*arr[i]) using rotations is 43