logo

TechCodeview

Найбільший добуток підмасиву розміром k

Спробуйте на GfG Practice ' title= #practiceLinkDiv { display: none !important; }

Дано масив, що складається з n натуральних чисел і цілого k. Знайдіть найбільший підмасив продукту розміром k, тобто знайдіть максимальний продукт із k суміжних елементів у масиві, де k<= n.
Приклади:  

    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 Найбільший продукт Спробуйте!

Підхід грубої сили:



Ми перебираємо всі підмасиви розміру k за допомогою двох вкладених циклів. Зовнішній цикл проходить від 0 до n-k, а внутрішній — від i до i+k-1. Ми обчислюємо добуток кожного підмасиву та оновлюємо максимальний знайдений добуток. Нарешті ми повертаємо максимальний продукт.

Ось кроки для вищезазначеного підходу:

  1. Ініціалізуйте змінну maxProduct як INT_MIN, яка представляє найменше можливе ціле значення.
  2. Перебирайте всі підмасиви розміром k за допомогою двох вкладених циклів.
  3. Зовнішній цикл проходить від 0 до n-k.
  4. Внутрішній цикл проходить від i до i+k-1, де i є початковим індексом підмасиву.
  5. Обчислити добуток поточного підмасиву за допомогою внутрішнього циклу.
  6. Якщо продукт більший за maxProduct, оновіть maxProduct до поточного продукту.
  7. Поверніть maxProduct як результат.

Нижче наведено код вищезазначеного підходу:



C++ 
// C++ program to find the maximum product of a subarray // of size k. #include    using 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; }
Java 
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));  } }
Python3 
# 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
C# 
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));  } }
JavaScript 
// 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));

Вихід 
4608 720 80

Часова складність: O(n*k), де n — довжина вхідного масиву, а k — розмір підмасиву, для якого ми знаходимо максимальний продукт.
Допоміжний простір: O(1), оскільки ми використовуємо лише постійну кількість додаткового простору для зберігання максимального добутку та добутку поточного підмасиву.

Метод 2 (Ефективний: O(n))  
Ми можемо розв’язати її в O(n), використовуючи той факт, що добуток підмасиву розміром k можна обчислити за O(1) часу, якщо у нас є добуток попереднього підмасиву. 
 

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]


Таким чином ми можемо обчислити максимальний добуток підмасиву розміром k лише за один обхід. Нижче наведено C++ реалізацію ідеї.



вирівняти зображення css
C++ 
// C++ program to find the maximum product of a subarray // of size k. #include    using 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; }
Java 
// 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
Python3 
# 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# 
// 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.
JavaScript 
<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 
 // 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. ?>

Вихід 
4608 720 80

Допоміжний простір: O(1) оскільки додатковий простір не використовується.
Цю статтю надав Ашутош Кумар .