크기 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  가장 큰 제품    시도해 보세요!       무차별 접근 방식:    
   두 개의 중첩 루프를 사용하여 크기가 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))        
 이전 하위 배열의 곱이 사용 가능한 경우 크기 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]    
 이러한 방식으로 우리는 단 한 번의 순회만으로 최대 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)    추가 공간이 사용되지 않기 때문입니다.   
 이 기사는 기고자:       아슈토시 쿠마르      .