数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学在C++中，只允许对给定数组进行旋转操作，求Sum(i*arr[i])的最大值
在这个问题中，我们得到一个包含n个元素的数组arr[]。我们需要在只允许对给定数组进行旋转操作的情况下，找到Sum(i*arr[i])的最大值。为了找到(i*arr[i])的最大和，我们可以进行任意次数的旋转。
让我们举个例子来理解这个问题：
输入
arr[] = {4, 1, 3, 7, 2}输出
43
解释
我们将数组旋转一次以获得最大值，旋转后的数组将是{2, 4, 1, 3, 7}
Sum = 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
更新于：2021年3月12日
121 次查看
广告