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
热门推荐
10 朋友新年祝福语大全 简短
11 新年祝福语简短大方兔年
12 搬新家礼物祝福语简短
13 同学见面花束祝福语简短
14 五一假期祝福语幽默简短
15 离职欢送敬酒祝福语简短
16 对学弟的祝福语简短
17 考老师辞职祝福语简短
18 祝福语驱散霉运的话简短