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

<?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
?>

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!