Lielākais k izmēra apakšplūsmas reizinājums
Izmēģiniet to GfG Practice 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Dots masīvs, kas sastāv no n pozitīviem veseliem skaitļiem un vesela skaitļa k. Atrodiet lielāko produktu apakšgrupu ar izmēru k, t.i., atrodiet maksimālo k blakus esošo elementu produkciju masīvā, kur k <= n.
Piemēri:
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 Lielākais produkts Izmēģiniet to!Brutālā spēka pieeja:
Mēs atkārtojam visus k izmēra apakšblokus, izmantojot divas ligzdotas cilpas. Ārējā cilpa iet no 0 līdz n-k un iekšējā cilpa no i līdz i+k-1. Mēs aprēķinām katra apakšmasīva reizinājumu un atjauninām līdz šim atrasto maksimālo produktu. Visbeidzot mēs atgriežam maksimālo produktu.
Tālāk ir norādītas iepriekš minētās pieejas darbības.
- Inicializējiet mainīgo maxProduct uz INT_MIN, kas apzīmē mazāko iespējamo veselo skaitli.
- Atkārtojiet visus k izmēra apakšblokus, izmantojot divas ligzdotas cilpas.
- Ārējā cilpa iet no 0 līdz n-k.
- Iekšējā cilpa iet no i līdz i+k-1, kur i ir apakšgrupas sākuma indekss.
- Aprēķiniet pašreizējā apakšgrupas reizinājumu, izmantojot iekšējo cilpu.
- Ja produkts ir lielāks par maxProduct, atjauniniet maxProduct uz pašreizējo produktu.
- Atgrieziet maxProduct kā rezultātu.
Tālāk ir norādīts iepriekš minētās pieejas kods:
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 )); } }
Izvade4608 720 80Laika sarežģītība: O(n*k) kur n ir ievades masīva garums un k ir apakšmasīva izmērs, kuram mēs atrodam maksimālo reizinājumu.
Palīgtelpa: O(1), jo mēs izmantojam tikai nemainīgu papildu vietas daudzumu, lai saglabātu maksimālo reizinājumu un pašreizējā apakšgrupas reizinājumu.2. metode (efektīva: O(n))
Mēs to varam atrisināt O(n), izmantojot faktu, ka k izmēra apakšgrupas reizinājumu var aprēķināt O(1) laikā, ja mums ir pieejams iepriekšējā apakšgrupas reizinājums.
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++
Tādā veidā mēs varam aprēķināt maksimālo k izmēra apakšgrupas produktu tikai vienā šķērsošanā. Zemāk ir C++ idejas realizācija.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>
Izvade4608 720 80Palīgtelpa: O(1) jo netiek izmantota papildu vieta.
Šī raksta autors ir Ašūts Kumars .
