Programa C++ para la suma máxima de i*arr[i] entre todas las rotaciones de una array dada

Dada una array arr[] de n enteros, encuentre el máximo que maximiza la suma del valor de i*arr[i] donde i varía de 0 a n-1.

Ejemplos:  

Input: arr[] = {8, 3, 1, 2}
Output: 29
Explanation: Lets look at all the rotations,
{8, 3, 1, 2} = 8*0 + 3*1 + 1*2 + 2*3 = 11
{3, 1, 2, 8} = 3*0 + 1*1 + 2*2 + 8*3 = 29
{1, 2, 8, 3} = 1*0 + 2*1 + 8*2 + 3*3 = 27
{2, 8, 3, 1} = 2*0 + 8*1 + 3*2 + 1*3 = 17

Input: arr[] = {3, 2, 1}
Output: 7
Explanation: Lets look at all the rotations,
{3, 2, 1} = 3*0 + 2*1 + 1*2 = 4
{2, 1, 3} = 2*0 + 1*1 + 3*2 = 7
{1, 3, 2} = 1*0 + 3*1 + 2*2 = 7

Método 1 : este método analiza la solución ingenua que requiere una cantidad de tiempo O (n 2 ).
La solución implica encontrar la suma de todos los elementos de la array en cada rotación y luego decidir el valor de suma máxima. 

  • Enfoque: una solución simple es probar todas las rotaciones posibles. Calcule la suma de i*arr[i] para cada rotación y devuelva la suma máxima.
  • Algoritmo:
    1. Gire la array para todos los valores de 0 a n.
    2. Calcular la suma de cada rotación.
    3. Compruebe si la suma máxima es mayor que la suma actual y luego actualice la suma máxima.
  • Implementación:

C++

// A Naive C++ program to find maximum sum rotation
#include<bits/stdc++.h>
 
using namespace std;
 
// Returns maximum value of i*arr[i]
int maxSum(int arr[], int n)
{
   // Initialize result
   int res = INT_MIN;
 
   // Consider rotation beginning with i
   // for all possible values of i.
   for (int i=0; i<n; i++)
   {
 
     // Initialize sum of current rotation
     int curr_sum = 0;
 
     // Compute sum of all values. We don't
     // actually rotate the array, instead of that we compute the
     // sum by finding indexes when arr[i] is
     // first element
     for (int j=0; j<n; j++)
     {
         int index = (i+j)%n;
         curr_sum += j*arr[index];
     }
 
     // Update result if required
     res = max(res, curr_sum);
   }
 
   return res;
}
 
// Driver code
int main()
{
    int arr[] = {8, 3, 1, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << maxSum(arr, n) << endl;
    return 0;
}

Producción :

29
  • Análisis de  
    Complejidad: Complejidad de Tiempo: O(n 2 ), ya que estamos usando bucles anidados.
    Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Método 2 : Este método analiza la solución eficiente que resuelve el problema en tiempo O(n). En la solución ingenua, los valores se calcularon para cada rotación. Entonces, si eso se puede hacer en tiempo constante, la complejidad disminuirá.

  • Enfoque: El enfoque básico es calcular la suma de la nueva rotación a partir de las rotaciones anteriores. Esto trae a colación una similitud en la que solo los multiplicadores del primer y último elemento cambian drásticamente y el multiplicador de todos los demás elementos aumenta o disminuye en 1. Entonces, de esta manera, la suma de la próxima rotación se puede calcular a partir de la suma de la rotación actual.
  • Algoritmo: 
    La idea es calcular el valor de una rotación usando valores de la rotación anterior. Cuando una array se rota en uno, los siguientes cambios ocurren en la suma de i*arr[i]. 
    1. El multiplicador de arr[i-1] cambia de 0 a n-1, es decir, arr[i-1] * (n-1) se suma al valor actual.
    2. Los multiplicadores de otros términos se reducen en 1. Es decir, (cum_sum – arr[i-1]) se resta del valor actual donde cum_sum es la suma de todos los números.
next_val = curr_val - (cum_sum - arr[i-1]) + arr[i-1] * (n-1);

next_val = Value of ∑i*arr[i] after one rotation.
curr_val = Current value of ∑i*arr[i] 
cum_sum = Sum of all array elements, i.e., ∑arr[i].

Lets take example {1, 2, 3}. Current value is 1*0+2*1+3*2
= 8. Shifting it by one will make it {2, 3, 1} and next value
will be 8 - (6 - 1) + 1*2 = 5 which is same as 2*0 + 3*1 + 1*2
  • Implementación : 
     

C++

// An efficient C++ program to compute
// maximum sum of i*arr[i]
#include<bits/stdc++.h>
 
using namespace std;
 
int maxSum(int arr[], int n)
{
    // Compute sum of all array elements
    int cum_sum = 0;
    for (int i=0; i<n; i++)
        cum_sum += arr[i];
 
    // Compute sum of i*arr[i] for initial
    // configuration.
    int curr_val = 0;
    for (int i=0; i<n; i++)
        curr_val += i*arr[i];
 
    // Initialize result
    int res = curr_val;
 
    // Compute values for other iterations
    for (int i=1; i<n; i++)
    {
        // Compute next value using previous
        // value in O(1) time
        int next_val = curr_val - (cum_sum - arr[i-1])
                       + arr[i-1] * (n-1);
 
        // Update current value
        curr_val = next_val;
 
        // Update result if required
        res = max(res, next_val);
    }
 
    return res;
}
 
// Driver code
int main()
{
    int arr[] = {8, 3, 1, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << maxSum(arr, n) << endl;
    return 0;
}

Producción:

29
  • Análisis de complejidad: 
    • Complejidad temporal: O(n). 
      Dado que se necesita un ciclo de 0 an para verificar todas las rotaciones y la suma de la rotación actual se calcula a partir de las rotaciones anteriores en tiempo O (1 ).
    • Espacio Auxiliar: O(1). 
      Como no se requiere espacio adicional, la complejidad del espacio será O (1)
  • Enfoque: supongamos el caso de una array ordenada. Como sabemos, para una array, la suma máxima será cuando la array se ordene en orden ascendente. En el caso de una array rotada ordenada, podemos rotar la array para hacerla en orden ascendente. Entonces, en este caso, se necesita encontrar el elemento pivote después del cual se puede calcular la suma máxima.
  • Algoritmo: 
    1. Encuentre el pivote de la array : si arr[i] > arr[(i+1)%n] entonces es el elemento pivote. (i+1)%n se utiliza para comprobar el último y el primer elemento.
    2. Después de obtener el pivote, la suma se puede calcular encontrando la diferencia con el pivote que será el multiplicador y multiplicándolo con el elemento actual mientras se calcula la suma.
  • Implementaciones:
  • Análisis de complejidad: 
    • Complejidad de tiempo: O (n) 
      Ya que solo se necesitaba un ciclo para atravesar de 0 an para encontrar el pivote. Para encontrar la suma se necesitaba otro bucle, por lo que la complejidad sigue siendo O(n) .
    • Espacio Auxiliar : O(1). 
      No requerimos espacio adicional para que el espacio auxiliar sea O (1)

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *