C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++の特定の配列のすべてのローテーションにおけるi*arr[i]の最大合計


この問題では、配列arrが与えられます。私たちのタスクは、C++で指定された配列のすべてのローテーションの中でi*arr[i]の最大合計を見つけるプログラムを作成することです。

プログラムの説明 −ここでは、配列のすべての要素の合計に、ローテーションのインデックス{i *arr[i]}を掛けたものの最大合計を求めます。

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

入力 −配列arr ={4、8、1、5}

出力 − 37

説明

All rotations with the sum of i*arr[i] :
{4, 8, 1, 5} = 4*0 + 8*1 + 1*2 + 5*3 = 25
{8, 1, 5, 4} = 8*0 + 1*1 + 5*2 + 4*3 = 23
{1, 5, 4, 8} = 1*0 + 5*1 + 4*2 + 8*3 = 37
{5, 4, 8, 1} = 5*0 + 4*1 + 8*2 + 1*3 = 23
The max sum of i*arr[i] is for third rotation.

この問題の簡単な解決策は、すべての要素の合計に各回転のインデックスを掛けたものを計算することです。そして、すべての回転の合計の最大値を見つけます。このために、配列をn回ローテーションし、それぞれの合計を計算し、現在のローテーションの合計が最後のローテーションよりも大きい場合は、maxSum変数の合計を格納します。

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

#include<iostream>
using namespace std;
int findMax(int a, int b){
   if(a>b)
      return a;
return b;
}
int calculateMaxSum(int arr[], int n){
   int maxSum = 0, sum = 0;
   for (int i=0; i<n; i++){
      sum = 0;
      for (int j=0; j<n; j++){
         int index = (i+j)%n;
         sum += j*arr[index];
      }
      maxSum = findMax(maxSum, sum);
   }
   return maxSum;
}
int main(){
   int arr[] = {4, 8, 1, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum sum of all the rotation of the array is "<<calculateMaxSum(arr, n);
   return 0;
}

出力

The maximum sum of all the rotation of the array is 37

効率的な解決策は、前の回転を使用して次の回転の合計を計算することです。式を使用します

nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1]*(n-1)

この式を使用して、nextSumを見つけ、ループ本体の最後で、nextSumがmaxSumより大きいかどうかを確認します。大きい場合は、maxSum=nextSumです。

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

#include<iostream>
using namespace std;
int findMax(int a, int b){
   if(a > b)
      return a;
   return b;
}
int calculateMaxSum(int arr[], int n){
   int arraySum = 0, currentSum = 0, nextSum ;
   for (int i=0; i<n; i++){
      arraySum += arr[i];
      currentSum += i*arr[i];
   }
   int maxSum = currentSum;
   for (int i=1; i<n; i++){
      nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1] * (n1);
      currentSum = nextSum;
      maxSum = findMax(maxSum, nextSum);
   }
   return maxSum;
}
int main(){
   int arr[] = {4, 8, 1, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum sum of all the rotation of the array is "<<calculateMaxSum(arr, n);
   return 0;
}

出力

The maximum sum of all the rotation of the array is 37

  1. C++の特定のバイナリツリーのすべてのレベルにおける非リーフノードの最大合計

    この問題では、二分木が与えられます。私たちのタスクは、c++で指定されたバイナリツリーのすべてのレベルから非リーフノードの最大合計を見つけるプログラムを作成することです。 問題の説明 −ツリーのすべての非リーフノードとすべてのレベルの合計を計算してから、最大合計を出力します。 問題を理解するために例を見てみましょう 入力 − 出力 − 9 説明 −各レベルの非リーフノードの合計- Level 1: 4 Level 2: 1+2 = 3 Level 3: 9 (4, 7 are leaf nodes) Level 4: 0 この問題を解決するには、バイナリツリーのレベル順ト

  2. C ++の合計配列パズル?

    ここでは、配列に関連する1つの興味深い問題を確認します。 n個の要素を持つ配列があります。 n個の要素の別の配列を作成する必要があります。ただし、2番目の配列のi番目の位置は、i番目の要素を除く最初の配列のすべての要素の合計を保持します。そして、1つの制約は、この問題では減算演算子を使用できないことです。 減算演算を使用できれば、すべての要素の合計を取得し、最初の配列のi番目の要素を減算して、2番目の配列のi番目の場所に格納することで、この問題を簡単に解決できます。 ここでは、毎回要素を追加することでこれを解決し、0..n-1のiについては、位置iの要素を無視します。ポイントを得るためのア