Prodotto più grande di un sottoarray di dimensione k
Provalo su GfG Practice 
#practiceLinkDiv { display: none! importante; }
#practiceLinkDiv { display: none! importante; } Dato un array composto da n interi positivi e un intero k. Trova il sottoarray prodotto più grande di dimensione k, ovvero trova il massimo prodotto di k elementi contigui nell'array dove k <= n.
Esempi:
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 Prodotto più grande Provalo!Approccio della forza bruta:
Iteriamo su tutti i sottoarray di dimensione k utilizzando due cicli nidificati. Il ciclo esterno va da 0 a n-k e il ciclo interno va da i a i+k-1. Calcoliamo il prodotto di ciascun sottoarray e aggiorniamo il prodotto massimo trovato finora. Infine restituiamo il prodotto massimo.
Ecco i passaggi per l'approccio sopra descritto:
- Inizializza una variabile maxProduct su INT_MIN che rappresenta il valore intero più piccolo possibile.
- Itera su tutti i sottoarray di dimensione k utilizzando due cicli nidificati.
- Il ciclo esterno va da 0 a n-k.
- Il ciclo interno va da i a i+k-1 dove i è l'indice iniziale del sottoarray.
- Calcola il prodotto del sottoarray corrente utilizzando il ciclo interno.
- Se il prodotto è maggiore di maxProduct, aggiorna maxProduct al prodotto corrente.
- Restituisce maxProduct come risultato.
Di seguito è riportato il codice dell'approccio precedente:
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 )); } }
Produzione4608 720 80Complessità temporale:
Spazio ausiliario: O(1) perché stiamo utilizzando solo una quantità costante di spazio aggiuntivo per memorizzare il prodotto massimo e il prodotto del sottoarray corrente.Metodo 2 (Efficace: O(n))
Possiamo risolverlo in O(n) sfruttando il fatto che il prodotto di un sottoarray di dimensione k può essere calcolato in tempo O(1) se abbiamo a disposizione il prodotto del sottoarray precedente.
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++
In questo modo possiamo calcolare il prodotto di sottoarray di dimensione k massima in un solo attraversamento. Di seguito è riportata l'implementazione C++ dell'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>
Produzione4608 720 80Spazio ausiliario: O(1) poiché non viene utilizzato spazio aggiuntivo.
Questo articolo è stato fornito da Ashutosh Kumar .
