Największy iloczyn podtablicy o rozmiarze k
Wypróbuj w praktyce GfG 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Biorąc pod uwagę tablicę składającą się z n dodatnich liczb całkowitych i liczby całkowitej k. Znajdź największą podtablicę iloczynów o rozmiarze k, tj. znajdź maksymalną produkcję k sąsiadujących elementów w tablicy, gdzie k <= n.
Przykłady:
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 Największy produkt Spróbuj!Podejście brutalnej siły:
Iterujemy po wszystkich podtablicach o rozmiarze k, używając dwóch zagnieżdżonych pętli. Zewnętrzna pętla biegnie od 0 do n-k, a wewnętrzna pętla biegnie od i do i+k-1. Obliczamy iloczyn każdej podtablicy i aktualizujemy maksymalny znaleziony do tej pory produkt. Na koniec zwracamy maksymalny produkt.
Oto kroki powyższego podejścia:
- Zainicjuj zmienną maxProduct na INT_MIN, która reprezentuje najmniejszą możliwą wartość całkowitą.
- Wykonaj iterację po wszystkich podtablicach o rozmiarze k, używając dwóch zagnieżdżonych pętli.
- Zewnętrzna pętla biegnie od 0 do n-k.
- Wewnętrzna pętla biegnie od i do i+k-1, gdzie i jest początkowym indeksem podtablicy.
- Oblicz iloczyn bieżącego podtablicy za pomocą pętli wewnętrznej.
- Jeśli produkt jest większy niż maxProduct, zaktualizuj maxProduct do bieżącego produktu.
- Jako wynik zwróć maxProduct.
Poniżej znajduje się kod powyższego podejścia:
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 )); } }
Wyjście4608 720 80Złożoność czasowa: O(n*k) gdzie n to długość tablicy wejściowej, a k to rozmiar podtablicy, dla której znajdujemy iloczyn maksymalny.
Przestrzeń pomocnicza: O(1), ponieważ używamy tylko stałej ilości dodatkowej przestrzeni do przechowywania iloczynu maksymalnego i iloczynu bieżącej podtablicy.Metoda 2 (wydajna: O(n))
Możemy to rozwiązać w O(n), korzystając z faktu, że iloczyn podtablicy o rozmiarze k można obliczyć w czasie O(1), jeśli mamy pod ręką iloczyn poprzedniego podtablicy.
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++
W ten sposób możemy obliczyć maksymalny iloczyn podtablicy o rozmiarze k tylko w jednym przejściu. Poniżej znajduje się implementacja tego pomysłu w 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 ) { // 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>
Wyjście4608 720 80Przestrzeń pomocnicza: O(1) ponieważ nie jest wykorzystywana żadna dodatkowa przestrzeń.
Współautorem tego artykułu jest Ashutosh Kumar .
