# 在只允許旋轉給定數組的情況下找到`Sum(i * arr[i])`的最大值 > 原文： [https://www.geeksforgeeks.org/find-maximum-value-of-sum-iarri-with-only-rotations-on-given-array-allowed/](https://www.geeksforgeeks.org/find-maximum-value-of-sum-iarri-with-only-rotations-on-given-array-allowed/) 給定一個數組，僅允許對數組進行旋轉操作。 我們可以根據需要旋轉數組多次。 返回`i * arr[i]`的總和的最大可能性。 **示例**： ``` Input: arr[] = {1, 20, 2, 10} Output: 72 We can 72 by rotating array twice. {2, 10, 1, 20} 20*3 + 1*2 + 10*1 + 2*0 = 72 Input: arr[] = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9}; Output: 330 We can 330 by rotating array 9 times. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 0*1 + 1*2 + 2*3 ... 9*10 = 330 ``` **我們強烈建議您最小化瀏覽器，然后自己嘗試。** 一個**簡單解決方案**是一個個地查找所有旋轉，檢查每個旋轉的總和并返回最大和。 該解決方案的時間復雜度為`O(n^2)`。 我們可以使用**有效解決方案**在`O(n)`時間內解決此問題。 令`R[j]`為`i * arr[i]`旋轉`j`的值。 該想法是根據先前旋轉來計算下一旋轉值，即，根據`R[j-1]`計算`R[j]`。 我們可以將結果的初始值計算為`R[0]`，然后繼續計算下一個旋轉值。 **如何從`R[j-1]`有效地計算`R[j]`？** 這可以在`O(1)`時間內完成。 以下是詳細信息。 ``` Let us calculate initial value of i*arr[i] with no rotation R0 = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] After 1 rotation arr[n-1], becomes first element of array, arr[0] becomes second element, arr[1] becomes third element and so on. R1 = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] R1 - R0 = arr[0] + arr[1] + ... + arr[n-2] - (n-1)*arr[n-1] After 2 rotations arr[n-2], becomes first element of array, arr[n-1] becomes second element, arr[0] becomes third element and so on. R2 = 0*arr[n-2] + 1*arr[n-1] +...+ (n-1)*arr[n-3] R2 - R1 = arr[0] + arr[1] + ... + arr[n-3] - (n-1)*arr[n-2] + arr[n-1] If we take a closer look at above values, we can observe below pattern Rj - Rj-1 = arrSum - n * arr[n-j] Where arrSum is sum of all array elements, i.e., arrSum = ∑ arr[i] 0<=i<=n-1 ``` 下面是完整的算法： ``` 1) Compute sum of all array elements. Let this sum be 'arrSum'. 2) Compute R0 by doing i*arr[i] for given array. Let this value be currVal. 3) Initialize result: maxVal = currVal // maxVal is result. // This loop computes Rj from Rj-1 4) Do following for j = 1 to n-1 ......a) currVal = currVal + arrSum-n*arr[n-j]; ......b) If (currVal > maxVal) maxVal = currVal 5) Return maxVal ``` 下面是上述想法的實現： ## C++ ```cpp // C++ program to find max value of i*arr[i] #include <iostream> using namespace std; // Returns max possible value of i*arr[i] int maxSum(int arr[], int n) { ????// Find array sum and i*arr[i] with no rotation ????int arrSum = 0;? // Stores sum of arr[i] ????int currVal = 0;? // Stores sum of i*arr[i] ????for (int i=0; i<n; i++) ????{ ????????arrSum = arrSum + arr[i]; ????????currVal = currVal+(i*arr[i]); ????} ????// Initialize result as 0 rotation sum ????int maxVal = currVal; ????// Try all rotations one by one and find ????// the maximum rotation sum. ????for (int j=1; j<n; j++) ????{ ????????currVal = currVal + arrSum-n*arr[n-j]; ????????if (currVal > maxVal) ????????????maxVal = currVal; ????} ????// Return result ????return maxVal; } // Driver program int main(void) { ????int arr[] = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9}; ????int n = sizeof(arr)/sizeof(arr[0]); ????cout << "\nMax sum is " << maxSum(arr, n); ????return 0; } ``` ## Java ```java // Java program to find max value of i*arr[i] import java.util.Arrays; class Test { ????static int arr[] = new int[]{10, 1, 2, 3, 4, 5, 6, 7, 8, 9}; ????// Returns max possible value of i*arr[i] ????static int maxSum() ????{ ????????// Find array sum and i*arr[i] with no rotation ????????int arrSum = 0;? // Stores sum of arr[i] ????????int currVal = 0;? // Stores sum of i*arr[i] ????????for (int i=0; i<arr.length; i++) ????????{ ????????????arrSum = arrSum + arr[i]; ????????????currVal = currVal+(i*arr[i]); ????????} ????????// Initialize result as 0 rotation sum ????????int maxVal = currVal; ????????// Try all rotations one by one and find ????????// the maximum rotation sum. ????????for (int j=1; j<arr.length; j++) ????????{ ????????????currVal = currVal + arrSum-arr.length*arr[arr.length-j]; ????????????if (currVal > maxVal) ????????????????maxVal = currVal; ????????} ????????// Return result ????????return maxVal; ????} ????// Driver method to test the above function ????public static void main(String[] args)? ????{ ????????System.out.println("Max sum is " + maxSum()); ????} } ``` ## Python ``` '''Python program to find maximum value of Sum(i*arr[i])''' # returns max possible value of Sum(i*arr[i]) def maxSum(arr): ????# stores sum of arr[i] ????arrSum = 0???? ????# stores sum of i*arr[i] ????currVal = 0 ????n = len(arr) ????for i in range(0, n): ????????arrSum = arrSum + arr[i] ????????currVal = currVal + (i*arr[i]) ????# initialize result ????maxVal = currVal ????# try all rotations one by one and find the maximum? ????# rotation sum ????for j in range(1, n): ????????currVal = currVal + arrSum-n*arr[n-j] ????????if currVal > maxVal: ????????????maxVal = currVal ????# return result ????return maxVal # test maxsum(arr) function arr = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9] print "Max sum is: ", maxSum(arr) ``` ## C# ```cs // C# program to find max value of i*arr[i] using System; class Test { ????static int []arr = new int[]{10, 1, 2, 3, 4, ??????????????????????????????????5, 6, 7, 8, 9}; ????// Returns max possible value of i*arr[i] ????static int maxSum() ????{ ????????// Find array sum and i*arr[i] ????????// with no rotation ????????int arrSum = 0; // Stores sum of arr[i] ????????int currVal = 0; // Stores sum of i*arr[i] ????????for (int i = 0; i < arr.Length; i++) ????????{ ????????????arrSum = arrSum + arr[i]; ????????????currVal = currVal + (i * arr[i]); ????????} ????????// Initialize result as 0 rotation sum ????????int maxVal = currVal; ????????// Try all rotations one by one and find ????????// the maximum rotation sum. ????????for (int j = 1; j < arr.Length; j++) ????????{ ????????????currVal = currVal + arrSum - arr.Length * ????????????????????????????????arr[arr.Length - j]; ????????????if (currVal > maxVal) ????????????????maxVal = currVal; ????????} ????????// Return result ????????return maxVal; ????} ????// Driver Code ????public static void Main()? ????{ ????????Console.WriteLine("Max sum is " + maxSum()); ????} } // This article is contributed by vt_m.? ``` ## PHP ```php <?php // PHP program to find max? // value of i*arr[i]? // Returns max possible? // value of i*arr[i] function maxSum($arr, $n) { ????// Find array sum and ????// i*arr[i] with no rotation ????// Stores sum of arr[i] ????$arrSum = 0;? ????// Stores sum of i*arr[i] ????$currVal = 0;? ????for ($i = 0; $i < $n; $i++) ????{ ????????$arrSum = $arrSum + $arr[$i]; ????????$currVal = $currVal +? ??????????????????($i * $arr[$i]); ????} ????// Initialize result as ????// 0 rotation sum ????$maxVal = $currVal; ????// Try all rotations one? ????// by one and find the? ????// maximum rotation sum. ????for ($j = 1; $j < $n; $j++) ????{ ????????$currVal = $currVal + $arrSum -? ???????????????????$n * $arr[$n - $j]; ????????if ($currVal > $maxVal) ????????????$maxVal = $currVal; ????} ????// Return result ????return $maxVal; } // Driver Code $arr = array (10, 1, 2, 3, 4, ??????????????5, 6, 7, 8, 9); $n = sizeof($arr); echo "Max sum is " , ?????maxSum($arr, $n); // This code is contributed by m_kit ?> ``` **輸出**： ``` Max sum is 330 ``` **時間復雜度**： `O(n)` **輔助空間**： `O(1)`