Programa Java 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:

// 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());
    }
}

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!