在只允许旋转给定数组的情况下找到Sum(i * arr[i])的最大值 · GeeksForGeeks 中文系列教程

# 在只允许旋转给定数组的情况下找到`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)`