#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 4Recommended Practice Größtes Produkt Probieren Sie es aus!
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}
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++
// C++ program to find the maximum product of a subarray // of size k. #include
import 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)); } }
# 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 guptapratik
using 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)); } }
// 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. function findMaxProduct(arr k) { let maxProduct = Number.MIN_VALUE; const n = arr.length; for (let i = 0; i <= n - k; i++) { let product = 1; for (let j = i; j < i + k; j++) { product *= arr[j]; } maxProduct = Math.max(maxProduct product); } return maxProduct; } // Driver code const arr1 = [1 5 9 8 2 4 1 8 1 2]; let k = 6; console.log(findMaxProduct(arr1 k)); k = 4; console.log(findMaxProduct(arr1 k)); const arr2 = [2 5 8 1 1 3]; k = 3; console.log(findMaxProduct(arr2 k));
Ausgabe
4608 720 80
Zeitkomplexitä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]
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.
C++
// C++ program to find the maximum product of a subarray // of size k. #include
// 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 Kumar
# 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.
// 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.
<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>
// PHP 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. function findMaxProduct( $arr $n $k) { // Initialize the MaxProduct to // 1 as all elements // in the array are positive $MaxProduct = 1; for($i = 0; $i < $k; $i++) $MaxProduct *= $arr[$i]; $prev_product = $MaxProduct; // Consider every product // beginning with arr[i] // where i varies from 1 // to n-k-1 for($i = 1; $i < $n - $k; $i++) { $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 = array(1 5 9 8 2 4 1 8 1 2); $k = 6; $n = count($arr1); echo findMaxProduct($arr1 $n $k)'n' ; $k = 4; echo findMaxProduct($arr1 $n $k)'n'; $arr2 = array(2 5 8 1 1 3); $k = 3; $n = count($arr2); echo findMaxProduct($arr2 $n $k); // This code is contributed by anuj_67. ?> Ausgabe
4608 720 80
Hilfsraum: O(1) da kein zusätzlicher Platz beansprucht wird.
Dieser Artikel wurde verfasst von Ashutosh Kumar .