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 官宣新年祝福语简短