logo

TechCodeview

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

GfG Practice で試してみる ' title= #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 まで実行されます。各サブ配列の積を計算し、これまでに見つかった最大積を更新します。最後に最大積を返します。

上記のアプローチの手順は次のとおりです。

  1. 変数 maxProduct を、可能な最小の整数値を表す INT_MIN に初期化します。
  2. 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))  
以前の部分配列の積が利用可能な場合、サイズ 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) 余分なスペースが使用されていないためです。
この記事は次の寄稿者です アシュトシュ・クマール 。