資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學在C++中，只允許對給定陣列進行旋轉操作，求Sum(i*arr[i])的最大值
在這個問題中，我們得到一個包含n個元素的陣列arr[]。我們需要在只允許對給定陣列進行旋轉操作的情況下，找到Sum(i*arr[i])的最大值。為了找到(i*arr[i])的最大和，我們可以進行任意次數的旋轉。
讓我們舉個例子來理解這個問題：
輸入
arr[] = {4, 1, 3, 7, 2}輸出
43
解釋
我們將陣列旋轉一次以獲得最大值，旋轉後的陣列將是{2, 4, 1, 3, 7}
Sum = 0*2 + 1*4 + 2*1 + 3*3 + 4*7 = 0 + 4 + 2 + 9 + 28 = 43
解決方案方法
該問題的一個簡單的解決方案是將陣列旋轉n次。每次旋轉後，我們將找到sum(i*arr[i])並返回所有值的最大值。這很好，但時間複雜度為O(n2)。該問題一個更高效的解決方案是使用公式在不旋轉的情況下找到sum(i*arr[i])的值。
讓我們從數學上推匯出公式：
Let the sum after k rotation is equal to sum(k). sum(0) = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] => eq 1
現在，我們將旋轉值，之後和將變為：
sum(1) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] => eq 2 Subtracting eq2 - eq 1 sum(1) - sum(0) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] - 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] sum(1) - sum(0) = arr[0] + arr[1] + … arr[n-2 ] - (n - 1)*arr[n-1]
類似地，對於sum(2) - sum(1)：
sum(2) - sum(1) = arr[0] + arr[1] + …. arr[n - 3] - (n - 1)*arr[n-2] + arr[n-1]
將等式推廣：
sum(k) - sum(k-1) = arr[0] + arr[1] + …. Arr[n - 1] - (n)*arr[n - k]
使用這個公式，我們可以使用sum(0)找到sum(k)的值：
現在，在解決方案中，我們將找到陣列所有值的和，然後找到sum(0)的值。使用迴圈，我們將找到從1到n的所有sum(k)的值。並返回它們中的最大值。
程式說明了我們解決方案的工作原理：
示例
#include <iostream>
using namespace std;
int findMaxSumRotation(int arr[], int n){
int arrSum = 0;
int currSum = 0;
for (int i=0; i<n; i++){
arrSum = arrSum + arr[i];
currSum = currSum+(i*arr[i]);
}
int maxSum = currSum;
for (int j=1; j<n; j++){
currSum = currSum + arrSum-n*arr[n-j];
if (currSum > maxSum)
maxSum = currSum;
}
return maxSum;
}
int main(){
int arr[] = {4, 1, 3, 7, 2};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum value of sum(i*arr[i]) using rotations is "<<findMaxSumRotation(arr, n);
return 0;
}輸出
The maximum value of sum(i*arr[i]) using rotations is 43
更新於：2021年3月12日
121 次檢視
廣告