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