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 送给学长毕业祝福语简短