Saltar al contenido

Encuentre la suma máxima de la matriz realizando las operaciones dadas

Mejorar artículo

Guardar artículo

Me gusta el artículo

Mejorar artículo

Guardar artículo

Dada una matriz A[] de tamaño norte con elementos repetidos y todos los elementos de la matriz son positivos, la tarea es obtener el máximo suma aplicando las operaciones dadas:

  • Seleccione 2 índices aleatorios y seleccione 2 enteros (digamos X y j) tal que el producto de los elementos (x e y) es igual al producto de los elementos en el índice elegido.
  • Finalmente, reemplace el elemento de la matriz con X y j

Ejemplos:

Aporte: N = 3, A[] = {2, 3, 2}
Salida: 14
Explicación:

  • i = 1, j = 2, x = 6, y = 1 Después de aplicar la siguiente operación, obtenemos sum = 9 (6 + 1 + 2) y la matriz ahora se convierte en {6, 1, 2} ahora elegimos i nuevamente y j e intentaré encontrar i y j
  • i = 1, j = 3 la matriz se convierte en {12, 1, 1} la suma se convierte en 14, por lo que la suma máxima sigue siendo 14 y no podemos aumentar más.

Aporte: N = 2, A = {1, 3}
Salida: 4
Explicación:

  • i = 1, j = 2, x = 3, y = 1 Después de aplicar la siguiente operación obtenemos el arreglo sum = 4 ahora {3, 1}. Si volvemos a aplicar la operación, la matriz seguirá siendo la misma, por lo que la suma máxima será 4.

Acercarse: Implemente la siguiente idea para resolver el problema:

Mira las operaciones, entonces podemos ver que estamos multiplicando 2 elementos de la matriz, por lo que cada vez que seleccionamos un número entero como producto y el otro es 1. ¿Por qué? Debido a que esto satisface nuestra condición para la operación dada en la pregunta que es el producto de X y j debe ser igual al producto del elemento de la matriz en el índice que elegimos. Así que vamos a monitorear esta operación. n-1 tiempos y después del seguimiento de la operación n-1 veces obtenemos nuestra última cadena que consiste en n-1 unos y un elemento igual al producto de todos los elementos del arreglo.

Siga los pasos a continuación para implementar la idea anterior:

  • Calcular el producto de la matriz.
  • Agregar n-1 al producto final de la matriz.
  • La variable resultante será la máxima suma posible.

A continuación se muestra la implementación del enfoque anterior:

C++

#include <bits/stdc++.h>

using namespace std;

 

void maximumsum(int A[], int n)

{

 

    int k = 1;

 

    

    for (int i = 0; i < n; i++) {

        k *= A[i];

    }

 

    

    k += n - 1;

 

    

    cout << k << endl;

}

 

int main()

{

 

    int n = 3;

    int A[] = { 2, 3, 2 };

 

    

    maximumsum(A, n);

 

    return 0;

}

Complejidad del tiempo: A)
cuarto auxiliar: O(1)