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 好听的元旦简短祝福语