在只允许旋转给定数组的情况下找到Sum(i * arr[i])的最大值
给定一个数组，仅允许对数组进行旋转操作。 我们可以根据需要旋转数组多次。 返回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++
// 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 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#
// 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 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)。
版权属于：月萌API www.moonapi.com，转载请注明出处
