Programa C++ para encontrar el valor máximo de Sum (i * arr [i]) con solo rotaciones en una array dada permitida

Dada una array, solo se permite la operación de rotación en la array. Podemos rotar la array tantas veces como queramos. Devuelve la suma máxima posible de i*arr[i].

Ejemplos:  

Input: arr[] = {1, 20, 2, 10}
Output: 72
We can get 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 get 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

Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Una solución simple es encontrar todas las rotaciones una por una, verificar la suma de cada rotación y devolver la suma máxima. La complejidad temporal de esta solución es O(n ² ). 

Podemos resolver este problema en tiempo O(n) usando una Solución Eficiente . 
Sea R _j el valor de i*arr[i] con j rotaciones. La idea es calcular el valor de la siguiente rotación a partir de la rotación anterior, es decir, calcular R _j a partir de R _j-1 . Podemos calcular el valor inicial del resultado como R ₀ y luego seguir calculando los siguientes valores de rotación. 

¿Cómo calcular eficientemente R _j a partir de R _j-1 ?  
Esto se puede hacer en tiempo O(1). A continuación se muestran los detalles.  

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 

A continuación se muestra el algoritmo completo: 

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

A continuación se muestra la implementación de la idea anterior:

// 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 << "
Max sum is " << maxSum(arr, n);
    return 0;
}

Producción : 

Max sum is 330

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(1)

¡Consulte el artículo completo sobre Encontrar el valor máximo de Sum(i*arr[i]) con solo rotaciones en una array dada permitida para obtener más detalles!