Encuentre el valor máximo de Sum(i*arr[i]) con solo rotaciones en una array dada permitida

Dada una array arr[] de tamaño N , la tarea es encontrar la suma máxima posible de i*arr[i] cuando la array se puede rotar cualquier número de veces.

Ejemplos:  

Entrada: arr[] = {1, 20, 2, 10}
Salida: 72. Podemos obtener 72 rotando la array dos veces.
{2, 10, 1, 20}
20*3 + 1*2 + 10*1 + 2*0 = 72

Entrada: arr[] = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Salida: 330
Podemos obtener 330 girando la array 9 veces.
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
0*1 + 1*2 + 2*3 … 9*10 = 330

Enfoque ingenuo:  La idea básica de este enfoque es 

Encuentre todas las rotaciones una por una, verifique la suma de cada rotación y devuelva la suma máxima. 

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1) 

Enfoque Eficiente: La idea es la siguiente:

Sea R _j el valor de i*arr[i] con j rotaciones. 

• La idea es calcular el siguiente valor de 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. 

Calculemos el valor inicial de i*arr[i] sin rotación
R ₀ = 0*arr[0] + 1*arr[1] +…+ (n-1)*arr[n-1]

Después de 1 rotación arr[n-1] , se convierte en el primer elemento de la array, 

• arr[0] se convierte en el segundo elemento, arr[1] se convierte en el tercer elemento y así sucesivamente.
• R ₁ = 0*arr[n-1] + 1*arr[0] +…+ (n-1)*arr[n-2]
• R ₁ – R ₀ = arr[0] + arr[1] + … + arr[n-2] – (n-1)*arr[n-1]

Después de 2 rotaciones arr[n-2] , se convierte en el primer elemento de la array, 

• arr[n-1] se convierte en el segundo elemento, arr[0] se convierte en el tercer elemento y así sucesivamente.
• R ₂ = 0*arr[n-2] + 1*arr[n-1] +…+ (n-1)*arr[n-3]
• R ₂ – R ₁ = arr[0] + arr[1] + … + arr[n-3] – (n-1)*arr[n-2] + arr[n-1]

Si observamos más de cerca los valores anteriores, podemos observar el siguiente patrón
R _j – R _j-1 = arrSum – n * arr[nj] ,
donde arrSum es la suma de todos los elementos de la array, es decir,  arrSum = ∑ arr[i] , 0 ≤ yo ≤ N-1

Siga la siguiente ilustración para una mejor comprensión. 

Ilustración:

Dado arr[]={10, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 

arrSum = 55 , currVal = suma de (i*arr[i]) =   285
En cada iteración, currVal es currVal = currVal + arrSum-n*arr[nj] ,

1ra rotación: currVal = 285 + 55 – (10 * 9) = 250

2da rotación: currVal = 285 + 55 – (10 * 8) = 260

3ra rotación: currVal = 285 + 55 – (10 * 7) = 270
.
.
.
Última rotación: currVal = 285 + 55 – (10 * 1) = 330

El currVal anterior era 285, ahora se convierte en 330.
Es el valor máximo que podemos encontrar, por lo tanto, devuelve 330 .

Siga los pasos mencionados a continuación para implementar el enfoque anterior:

• Calcule la suma de todos los elementos de la array. Sea esta suma ‘ arrSum ‘.
• Calcule R ₀ para la array dada. Sea este valor currVal .
• Bucle de j = 1 a N-1 para calcular el valor de cada rotación:
  • Actualice el currVal usando la fórmula mencionada anteriormente.
  • Actualice la suma máxima en consecuencia en cada paso.
• Devuelve el valor máximo como la respuesta requerida.

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

// 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 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
if __name__ == '__main__':
    arr = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    print "Max sum is: ", maxSum(arr)

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

<script>
// JavaScript 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
    let arrSum = 0; // Stores sum of arr[i]
    let currVal = 0; // Stores sum of i*arr[i]
    for (let i=0; i<n; i++)
    {
        arrSum = arrSum + arr[i];
        currVal = currVal+(i*arr[i]);
    }
 
    // Initialize result as 0 rotation sum
    let maxVal = currVal;
 
    // Try all rotations one by one and find
    // the maximum rotation sum.
    for (let j=1; j<n; j++)
    {
        currVal = currVal + arrSum-n*arr[n-j];
        if (currVal > maxVal)
            maxVal = currVal;
    }
 
    // Return result
    return maxVal;
}
 
// Driver program
    let arr = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9];
    let n = arr.length;
    document.write("Max sum is " + maxSum(arr, n));
 
 
 
 
 
 
// This code is contributed by Surbhi Tyagi.
</script>

Max sum is 330

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)