#practiceLinkDiv { display: nenhum! Importante; }Dado um array que consiste em n inteiros positivos e um inteiro k. Encontre a maior submatriz de produto de tamanho k, ou seja, encontre a produção máxima de k elementos contíguos na matriz onde k<= n.
Exemplos:
Input: arr[] = {1 5 9 8 2 4Recommended Practice Maior produto Experimente!
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}
Abordagem de força bruta:
Iteramos todas as submatrizes de tamanho k usando dois loops aninhados. O loop externo vai de 0 a nk e o loop interno vai de i a i+k-1. Calculamos o produto de cada subarray e atualizamos o produto máximo encontrado até o momento. Finalmente retornamos o produto máximo.
Aqui estão as etapas para a abordagem acima:
- Inicialize uma variável maxProduct com INT_MIN que representa o menor valor inteiro possível.
- Itere sobre todas as submatrizes de tamanho k usando dois loops aninhados.
- O loop externo vai de 0 a nk.
- O loop interno vai de i a i+k-1 onde i é o índice inicial do subarray.
- Calcule o produto da submatriz atual usando o loop interno.
- Se o produto for maior que maxProduct, atualize maxProduct para o produto atual.
- Retorne maxProduct como resultado.
Abaixo está o código da abordagem acima:
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));
Saída
4608 720 80
Complexidade de tempo: O(n*k) onde n é o comprimento da matriz de entrada e k é o tamanho da submatriz para a qual estamos encontrando o produto máximo.
Espaço Auxiliar: O(1) porque estamos usando apenas uma quantidade constante de espaço adicional para armazenar o produto máximo e o produto da submatriz atual.
Método 2 (eficiente: O(n))
Podemos resolvê-lo em O(n) usando o fato de que o produto de um subarranjo de tamanho k pode ser calculado em tempo O(1) se tivermos o produto do subarranjo anterior disponível conosco.
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]
Desta forma, podemos calcular o produto máximo do subarranjo de tamanho k em apenas uma travessia. Abaixo está a implementação da ideia em C++.
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. ?> Saída
4608 720 80
Espaço Auxiliar: O(1) já que nenhum espaço extra está sendo usado.
Este artigo é uma contribuição de Ashutosh Kumar .