資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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
更新於: 2020-06-03
444 次檢視
廣告