サイズ K の部分配列の最大の積

GfG Practice で試してみる
#practiceLinkDiv { 表示: なし !重要; }
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  最大の製品    試してみてください!       ブルートフォースアプローチ:    
   2 つのネストされたループを使用して、サイズ k のすべての部分配列を反復処理します。外側のループは 0 から n-k まで実行され、内側のループは i から i+k-1 まで実行されます。各サブ配列の積を計算し、これまでに見つかった最大積を更新します。最後に最大積を返します。  
   上記のアプローチの手順は次のとおりです。  
    変数 maxProduct を、可能な最小の整数値を表す INT_MIN に初期化します。  
  2 つのネストされたループを使用して、サイズ 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))        
 以前の部分配列の積が利用可能な場合、サイズ k の部分配列の積は O(1) 時間で計算できるという事実を利用して、O(n) で解くことができます。    
    
   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]    
 このようにして、1 回の走査だけで最大 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)    余分なスペースが使用されていないためです。   
 この記事は次の寄稿者です       アシュトシュ・クマール      。