Producto más grande de un subconjunto de tamaño k
Pruébalo en GfG Practice 
#practiceLinkDiv { mostrar: ninguno !importante; }
#practiceLinkDiv { mostrar: ninguno !importante; } Dada una matriz que consta de n números enteros positivos y un número entero k. Encuentre el subarreglo de producto más grande de tamaño k, es decir, encuentre el producto máximo de k elementos contiguos en el arreglo donde k <= n.
Ejemplos:
Input: arr[] = {1 5 9 8 2 4
1 8 1 2}
k = 6
Output: 4608
The subarray is {9 8 2 4 1 8}
Input: arr[] = {1 5 9 8 2 4 1 8 1 2}
k = 4
Output: 720
The subarray is {5 9 8 2}
Input: arr[] = {2 5 8 1 1 3};
k = 3
Output: 80
The subarray is {2 5 8} Recommended Practice Producto más grande ¡Pruébalo!Enfoque de fuerza bruta:
Iteramos sobre todos los subarreglos de tamaño k usando dos bucles anidados. El bucle exterior va de 0 a n-k y el bucle interior va de i a i+k-1. Calculamos el producto de cada subarreglo y actualizamos el producto máximo encontrado hasta el momento. Finalmente devolvemos el máximo producto.
Estos son los pasos para el enfoque anterior:
- Inicialice una variable maxProduct en INT_MIN que representa el valor entero más pequeño posible.
- Itere sobre todos los subarreglos de tamaño k utilizando dos bucles anidados.
- El bucle exterior va de 0 a n-k.
- El bucle interno va de i a i+k-1 donde i es el índice inicial del subarreglo.
- Calcule el producto del subarreglo actual usando el bucle interno.
- Si el producto es mayor que maxProduct, actualice maxProduct al producto actual.
- Devuelve maxProduct como resultado.
A continuación se muestra el código del enfoque anterior:
C++Java// C++ program to find the maximum product of a subarray // of size k. #includeusing namespace std ; // This function returns maximum product of a subarray // of size k in given array arr[0..n-1]. This function // assumes that k is smaller than or equal to n. int findMaxProduct ( int arr [] int n int k ) { int maxProduct = INT_MIN ; for ( int i = 0 ; i <= n - k ; i ++ ) { int product = 1 ; for ( int j = i ; j < i + k ; j ++ ) { product *= arr [ j ]; } maxProduct = max ( maxProduct product ); } return maxProduct ; } // Driver code int main () { int arr1 [] = { 1 5 9 8 2 4 1 8 1 2 }; int k = 6 ; int n = sizeof ( arr1 ) / sizeof ( arr1 [ 0 ]); cout < < findMaxProduct ( arr1 n k ) < < endl ; k = 4 ; cout < < findMaxProduct ( arr1 n k ) < < endl ; int arr2 [] = { 2 5 8 1 1 3 }; k = 3 ; n = sizeof ( arr2 ) / sizeof ( arr2 [ 0 ]); cout < < findMaxProduct ( arr2 n k ); return 0 ; } Python3import java.util.Arrays ; public class Main { // This function returns the maximum product of a subarray of size k in the given array // It assumes that k is smaller than or equal to the length of the array. static int findMaxProduct ( int [] arr int n int k ) { int maxProduct = Integer . MIN_VALUE ; for ( int i = 0 ; i <= n - k ; i ++ ) { int product = 1 ; for ( int j = i ; j < i + k ; j ++ ) { product *= arr [ j ] ; } maxProduct = Math . max ( maxProduct product ); } return maxProduct ; } // Driver code public static void main ( String [] args ) { int [] arr1 = { 1 5 9 8 2 4 1 8 1 2 }; int k = 6 ; int n = arr1 . length ; System . out . println ( findMaxProduct ( arr1 n k )); k = 4 ; System . out . println ( findMaxProduct ( arr1 n k )); int [] arr2 = { 2 5 8 1 1 3 }; k = 3 ; n = arr2 . length ; System . out . println ( findMaxProduct ( arr2 n k )); } }C## Python Code def find_max_product ( arr k ): max_product = float ( '-inf' ) # Initialize max_product to negative infinity n = len ( arr ) # Get the length of the input array # Iterate through the array with a window of size k for i in range ( n - k + 1 ): product = 1 # Initialize product to 1 for each subarray for j in range ( i i + k ): product *= arr [ j ] # Calculate the product of the subarray max_product = max ( max_product product ) # Update max_product if necessary return max_product # Return the maximum product of a subarray of size k # Driver code if __name__ == '__main__' : arr1 = [ 1 5 9 8 2 4 1 8 1 2 ] k = 6 print ( find_max_product ( arr1 k )) # Output 25920 k = 4 print ( find_max_product ( arr1 k )) # Output 1728 arr2 = [ 2 5 8 1 1 3 ] k = 3 print ( find_max_product ( arr2 k )) # Output 80 # This code is contributed by guptapratikJavaScriptusing System ; public class GFG { // This function returns the maximum product of a subarray of size k in the given array // It assumes that k is smaller than or equal to the length of the array. static int FindMaxProduct ( int [] arr int n int k ) { int maxProduct = int . MinValue ; for ( int i = 0 ; i <= n - k ; i ++ ) { int product = 1 ; for ( int j = i ; j < i + k ; j ++ ) { product *= arr [ j ]; } maxProduct = Math . Max ( maxProduct product ); } return maxProduct ; } // Driver code public static void Main ( string [] args ) { int [] arr1 = { 1 5 9 8 2 4 1 8 1 2 }; int k = 6 ; int n = arr1 . Length ; Console . WriteLine ( FindMaxProduct ( arr1 n k )); k = 4 ; Console . WriteLine ( FindMaxProduct ( arr1 n k )); int [] arr2 = { 2 5 8 1 1 3 }; k = 3 ; n = arr2 . Length ; Console . WriteLine ( FindMaxProduct ( arr2 n k )); } }
Producción4608 720 80Complejidad del tiempo: O(n*k) donde n es la longitud de la matriz de entrada y k es el tamaño de la submatriz para la cual estamos encontrando el producto máximo.
Espacio Auxiliar: O(1) porque solo estamos usando una cantidad constante de espacio adicional para almacenar el producto máximo y el producto del subarreglo actual.Método 2 (Eficiente: O(n))
Podemos resolverlo en O(n) aprovechando el hecho de que el producto de un subarreglo de tamaño k se puede calcular en tiempo O(1) si tenemos disponible el producto del subarreglo anterior.
curr_product = (prev_product / arr[i-1]) * arr[i + k -1]
prev_product : Product of subarray of size k beginning
with arr[i-1]
curr_product : Product of subarray of size k beginning
with arr[i]C++
De esta manera podemos calcular el producto de submatriz de tamaño máximo k en un solo recorrido. A continuación se muestra la implementación en C++ de la idea.Java// C++ program to find the maximum product of a subarray // of size k. #includeusing namespace std ; // This function returns maximum product of a subarray // of size k in given array arr[0..n-1]. This function // assumes that k is smaller than or equal to n. int findMaxProduct ( int arr [] int n int k ) { // Initialize the MaxProduct to 1 as all elements // in the array are positive int MaxProduct = 1 ; for ( int i = 0 ; i < k ; i ++ ) MaxProduct *= arr [ i ]; int prev_product = MaxProduct ; // Consider every product beginning with arr[i] // where i varies from 1 to n-k-1 for ( int i = 1 ; i <= n - k ; i ++ ) { int curr_product = ( prev_product / arr [ i -1 ]) * arr [ i + k -1 ]; MaxProduct = max ( MaxProduct curr_product ); prev_product = curr_product ; } // Return the maximum product found return MaxProduct ; } // Driver code int main () { int arr1 [] = { 1 5 9 8 2 4 1 8 1 2 }; int k = 6 ; int n = sizeof ( arr1 ) / sizeof ( arr1 [ 0 ]); cout < < findMaxProduct ( arr1 n k ) < < endl ; k = 4 ; cout < < findMaxProduct ( arr1 n k ) < < endl ; int arr2 [] = { 2 5 8 1 1 3 }; k = 3 ; n = sizeof ( arr2 ) / sizeof ( arr2 [ 0 ]); cout < < findMaxProduct ( arr2 n k ); return 0 ; } Python3// Java program to find the maximum product of a subarray // of size k import java.io.* ; import java.util.* ; class GFG { // Function returns maximum product of a subarray // of size k in given array arr[0..n-1]. This function // assumes that k is smaller than or equal to n. static int findMaxProduct ( int arr [] int n int k ) { // Initialize the MaxProduct to 1 as all elements // in the array are positive int MaxProduct = 1 ; for ( int i = 0 ; i < k ; i ++ ) MaxProduct *= arr [ i ] ; int prev_product = MaxProduct ; // Consider every product beginning with arr[i] // where i varies from 1 to n-k-1 for ( int i = 1 ; i <= n - k ; i ++ ) { int curr_product = ( prev_product / arr [ i - 1 ] ) * arr [ i + k - 1 ] ; MaxProduct = Math . max ( MaxProduct curr_product ); prev_product = curr_product ; } // Return the maximum product found return MaxProduct ; } // driver program public static void main ( String [] args ) { int arr1 [] = { 1 5 9 8 2 4 1 8 1 2 }; int k = 6 ; int n = arr1 . length ; System . out . println ( findMaxProduct ( arr1 n k )); k = 4 ; System . out . println ( findMaxProduct ( arr1 n k )); int arr2 [] = { 2 5 8 1 1 3 }; k = 3 ; n = arr2 . length ; System . out . println ( findMaxProduct ( arr2 n k )); } } // This code is contributed by Pramod KumarC## Python 3 program to find the maximum # product of a subarray of size k. # This function returns maximum product # of a subarray of size k in given array # arr[0..n-1]. This function assumes # that k is smaller than or equal to n. def findMaxProduct ( arr n k ) : # Initialize the MaxProduct to 1 # as all elements in the array # are positive MaxProduct = 1 for i in range ( 0 k ) : MaxProduct = MaxProduct * arr [ i ] prev_product = MaxProduct # Consider every product beginning # with arr[i] where i varies from # 1 to n-k-1 for i in range ( 1 n - k + 1 ) : curr_product = ( prev_product // arr [ i - 1 ]) * arr [ i + k - 1 ] MaxProduct = max ( MaxProduct curr_product ) prev_product = curr_product # Return the maximum product found return MaxProduct # Driver code arr1 = [ 1 5 9 8 2 4 1 8 1 2 ] k = 6 n = len ( arr1 ) print ( findMaxProduct ( arr1 n k ) ) k = 4 print ( findMaxProduct ( arr1 n k )) arr2 = [ 2 5 8 1 1 3 ] k = 3 n = len ( arr2 ) print ( findMaxProduct ( arr2 n k )) # This code is contributed by Nikita Tiwari.JavaScript// C# program to find the maximum // product of a subarray of size k using System ; class GFG { // Function returns maximum // product of a subarray of // size k in given array // arr[0..n-1]. This function // assumes that k is smaller // than or equal to n. static int findMaxProduct ( int [] arr int n int k ) { // Initialize the MaxProduct // to 1 as all elements // in the array are positive int MaxProduct = 1 ; for ( int i = 0 ; i < k ; i ++ ) MaxProduct *= arr [ i ]; int prev_product = MaxProduct ; // Consider every product beginning // with arr[i] where i varies from // 1 to n-k-1 for ( int i = 1 ; i <= n - k ; i ++ ) { int curr_product = ( prev_product / arr [ i - 1 ]) * arr [ i + k - 1 ]; MaxProduct = Math . Max ( MaxProduct curr_product ); prev_product = curr_product ; } // Return the maximum // product found return MaxProduct ; } // Driver Code public static void Main () { int [] arr1 = { 1 5 9 8 2 4 1 8 1 2 }; int k = 6 ; int n = arr1 . Length ; Console . WriteLine ( findMaxProduct ( arr1 n k )); k = 4 ; Console . WriteLine ( findMaxProduct ( arr1 n k )); int [] arr2 = { 2 5 8 1 1 3 }; k = 3 ; n = arr2 . Length ; Console . WriteLine ( findMaxProduct ( arr2 n k )); } } // This code is contributed by anuj_67.PHP< script > // JavaScript program to find the maximum // product of a subarray of size k // Function returns maximum // product of a subarray of // size k in given array // arr[0..n-1]. This function // assumes that k is smaller // than or equal to n. function findMaxProduct ( arr n k ) { // Initialize the MaxProduct // to 1 as all elements // in the array are positive let MaxProduct = 1 ; for ( let i = 0 ; i < k ; i ++ ) MaxProduct *= arr [ i ]; let prev_product = MaxProduct ; // Consider every product beginning // with arr[i] where i varies from // 1 to n-k-1 for ( let i = 1 ; i <= n - k ; i ++ ) { let curr_product = ( prev_product / arr [ i - 1 ]) * arr [ i + k - 1 ]; MaxProduct = Math . max ( MaxProduct curr_product ); prev_product = curr_product ; } // Return the maximum // product found return MaxProduct ; } let arr1 = [ 1 5 9 8 2 4 1 8 1 2 ]; let k = 6 ; let n = arr1 . length ; document . write ( findMaxProduct ( arr1 n k ) + ' ' ); k = 4 ; document . write ( findMaxProduct ( arr1 n k ) + ' ' ); let arr2 = [ 2 5 8 1 1 3 ]; k = 3 ; n = arr2 . length ; document . write ( findMaxProduct ( arr2 n k ) + ' ' ); < /script>
Producción4608 720 80Espacio auxiliar: O(1) ya que no se utiliza espacio adicional.
Este artículo es una contribución de Ashutosh Kumar .
