НАЙБІЛЬШИЙ ДОБУТОК ПІДМАСИВУ РОЗМІРОМ K

Спробуйте на GfG Practice
#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. Ми обчислюємо добуток кожного підмасиву та оновлюємо максимальний знайдений добуток. Нарешті ми повертаємо максимальний продукт.  
   Ось кроки для вищезазначеного підходу:  
    Ініціалізуйте змінну maxProduct як INT_MIN, яка представляє найменше можливе ціле значення.  
  Перебирайте всі підмасиви розміром k за допомогою двох вкладених циклів.  
  Зовнішній цикл проходить від 0 до n-k.  
  Внутрішній цикл проходить від i до i+k-1, де i є початковим індексом підмасиву.  
  Обчислити добуток поточного підмасиву за допомогою внутрішнього циклу.  
  Якщо продукт більший за maxProduct, оновіть maxProduct до поточного продукту.  
  Поверніть 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++ реалізацію ідеї.  
 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)    оскільки додатковий простір не використовується.   
 Цю статтю надав       Ашутош Кумар      .