This can be done in O(1) time. Below are details.
Let us calculate initial value of iarr[i] with no rotation R0 = 0arr[0] + 1arr[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 = 0arr[n-1] + 1arr[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 = 0arr[n-2] + 1arr[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
Below is complete algorithm:
- Compute sum of all array elements. Let this sum be ‘arrSum’. 2) Compute R0 by doing iarr[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-narr[n-j]; …b) If (currVal > maxVal) maxVal = currVal 5) Return maxVal
Below is the implementation of above idea :
- 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;
}
Output :
Max sum is 330
Time Complexity : O(n)
Auxiliary Space : O(1)