查找 Sum( i*arr[i]) 的最大值，仅在 C++ 中允许给定数组上进行旋转!

2023-06-16 13:11:02 67

在这个问题中，我们得到一个由n个元素组成的数组arr[]。我们需要找到Sum(i*arr[i])的最大值，只允许在给定数组上旋转。为了找到(i*arr[i])的最大和，我们可以执行任意次数的旋转。

让我们举个例子来理解这个问题，

输入

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

输出结果

解释

我们将数组旋转一次以获得最大值，旋转后数组将是{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(k)使用sum(0)的值，

现在，在解决方案中，我们将找到数组所有值的总和，然后找到sum(0)的值。使用循环，我们将找到sum(k)从1到n的所有值。并返回其中的最大值。

程序来说明我们的解决方案的工作，

示例

#include 
using namespace std;
int findMaxSumRotation(int arr[], int n){
   int arrSum = 0;
   int currSum = 0;
   for (int i=0; i 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 "<输出结果The maximum value of sum(i*arr[i]) using rotations is 43

查找 Sum( i*arr[i]) 的最大值，仅在 C++ 中允许给定数组上进行旋转!

输入

解释

解决方法

示例

热门推荐

随机推荐