Größtes Produkt eines Subarrays der Größe k
Probieren Sie es bei GfG Practice aus 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Gegeben sei ein Array bestehend aus n positiven ganzen Zahlen und einer ganzen Zahl k. Finden Sie das größte Produkt-Subarray der Größe k, d. h. finden Sie die maximale Produktion von k zusammenhängenden Elementen im Array, wobei k <= n.
Beispiele:
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 Größtes Produkt Probieren Sie es aus!Brute-Force-Ansatz:
Wir iterieren über alle Subarrays der Größe k, indem wir zwei verschachtelte Schleifen verwenden. Die äußere Schleife verläuft von 0 bis n-k und die innere Schleife verläuft von i bis i+k-1. Wir berechnen das Produkt jedes Subarrays und aktualisieren das bisher gefundene maximale Produkt. Schließlich geben wir das maximale Produkt zurück.
Hier sind die Schritte für den oben genannten Ansatz:
- Initialisieren Sie eine Variable maxProduct mit INT_MIN, die den kleinstmöglichen ganzzahligen Wert darstellt.
- Iterieren Sie mithilfe von zwei verschachtelten Schleifen über alle Subarrays der Größe k.
- Die äußere Schleife läuft von 0 bis n-k.
- Die innere Schleife läuft von i bis i+k-1, wobei i der Startindex des Subarrays ist.
- Berechnen Sie das Produkt des aktuellen Subarrays mithilfe der inneren Schleife.
- Wenn das Produkt größer als maxProduct ist, aktualisieren Sie maxProduct auf das aktuelle Produkt.
- Geben Sie maxProduct als Ergebnis zurück.
Nachfolgend finden Sie den Code des obigen Ansatzes:
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 )); } }
Ausgabe4608 720 80Zeitkomplexität: O(n*k) wobei n die Länge des Eingabearrays und k die Größe des Unterarrays ist, für das wir das maximale Produkt finden.
Hilfsraum: O(1), weil wir nur eine konstante Menge an zusätzlichem Speicherplatz verwenden, um das maximale Produkt und das Produkt des aktuellen Subarrays zu speichern.Methode 2 (Effizient: O(n))
Wir können es in O(n) lösen, indem wir die Tatsache nutzen, dass das Produkt eines Subarrays der Größe k in O(1)-Zeit berechnet werden kann, wenn wir das Produkt des vorherigen Subarrays zur Verfügung haben.
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++
Auf diese Weise können wir das Subarray-Produkt mit der maximalen k-Größe in nur einem Durchlauf berechnen. Nachfolgend finden Sie die C++-Implementierung der Idee.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>
Ausgabe4608 720 80Hilfsraum: O(1) da kein zusätzlicher Platz beansprucht wird.
Dieser Artikel wurde verfasst von Ashutosh Kumar .
