大小为k的子阵列的最大乘积-yiteyi-C++库

给定一个由n个正整数和一个整数k组成的数组。求大小为k的最大乘积子数组，即求数组中k个连续元素的最大乘积，其中k<=n。 例如：

null

Input: arr[] = {1, 5, 9, 8, 2, 4,                 1, 8, 1, 2}        k = 6Output:   4608  The subarray is {9, 8, 2, 4, 1, 8}Input: arr[] = {1, 5, 9, 8, 2, 4, 1, 8, 1, 2}       k = 4Output:   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}

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法1（简单：O（n*k）） 一个幼稚的方法是逐个考虑大小k的所有子阵列。这种方法需要两个循环，因此复杂性为O（n*k）。 方法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 <bits/stdc++.h>                       
                         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.                       

PHP

                         <?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                                     ),                                     ""                                     ;                       
           
                                                 $k                                     = 4;                       
                                                 echo                                     findMaxProduct(                                     $arr1                                     ,                                     $n                                     ,                                     $k                                     ),                                     ""                                     ;                       
           
                                                 $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.                       
                         ?>                       

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) +                                     "</br>"                                     );                       
           
                                                 k = 4;                       
                                                 document.write(findMaxProduct(arr1, n, k) +                                     "</br>"                                     );                       
           
                                                 let arr2 = [2, 5, 8, 1, 1, 3];                       
                                                 k = 3;                       
                                                 n = arr2.length;                       
                                                 document.write(findMaxProduct(arr2, n, k) +                                     "</br>"                                     );                       
                                   
                         </script>                       

输出：

460872080

本文由 阿什图什·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章