给定一个数组和一个数字k，任务是计算大小为k的子数组中所有元素的乘积之和。 例如：
null
Input : arr[] = {1, 2, 3, 4, 5, 6} k = 3Output : 210Consider all subarrays of size k1*2*3 = 62*3*4 = 243*4*5 = 604*5*6 = 1206 + 24 + 60 + 120 = 210Input : arr[] = {1, -2, 3, -4, 5, 6} k = 2Output : -10Consider all subarrays of size k1*-2 = -2-2*3 = -63*-4 = -12-4*5 = -205*6 = 30-2 + -6 + -12 + -20+ 30 = -10
A. 天真的方法 就是生成大小为k的所有子数组，并将子数组中所有元素的乘积求和。
C++
// C++ program to find the sum of // product of all subarrays #include <iostream> using namespace std; // Function to calculate the sum of product int calcSOP( int arr[], int n, int k) { // Initialize sum = 0 int sum = 0; // Consider every subarray of size k for ( int i = 0; i <= n - k; i++) { int prod = 1; // Calculate product of all elements // of current subarray for ( int j = i; j < k + i; j++) prod *= arr[j]; // Store sum of all the products sum += prod; } // Return sum return sum; } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 3; cout << calcSOP(arr, n, k); return 0; } |
JAVA
// Java program to find the sum of // product of all subarrays class GFG { // Method to calculate the sum of product static int calcSOP( int arr[], int n, int k) { // Initialize sum = 0 int sum = 0 ; // Consider every subarray of size k for ( int i = 0 ; i <= n - k; i++) { int prod = 1 ; // Calculate product of all elements // of current subarray for ( int j = i; j < k + i; j++) prod *= arr[j]; // Store sum of all the products sum += prod; } // Return sum return sum; } // Driver method public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 }; int k = 3 ; System.out.println(calcSOP(arr, arr.length, k)); } } |
Python3
# python program to find the sum of # product of all subarrays # Function to calculate the sum of product def calcSOP(arr, n, k): # Initialize sum = 0 sum = 0 # Consider every subarray of size k for i in range ( 0 , (n - k) + 1 ): prod = 1 # Calculate product of all elements # of current subarray for j in range (i, k + i): prod = int (prod * arr[j]) # Store sum of all the products sum = sum + prod # Return sum return sum #Driver code arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] n = len (arr) k = 3 print (calcSOP(arr, n, k)) # This code is contributed by Sam007 |
C#
// C# program to find the sum of // product of all subarrays using System; public class GFG { // Method to calculate the sum of product static int calcSOP( int [] arr, int n, int k) { // Initialize sum = 0 int sum = 0; // Consider every subarray of size k for ( int i = 0; i <= n - k; i++) { int prod = 1; // Calculate product of all elements // of current subarray for ( int j = i; j < k + i; j++) prod *= arr[j]; // Store sum of all the products sum += prod; } // Return sum return sum; } // Driver method public static void Main() { int [] arr = {1, 2, 3, 4, 5, 6}; int k = 3; Console.WriteLine(calcSOP(arr, arr.Length, k)); } } // This code is contributed by Sam007 |
<?php// PHP program to find the sum of// product of all subarrays// Function to calculate// the sum of productfunction calcSOP($arr, $n, $k){ // Initialize sum = 0 $sum = 0; // Consider every subarray // of size k for ($i = 0; $i <= $n - $k; $i++) { $prod = 1; // Calculate product of all // elements of current subarray for ($j = $i; $j < $k + $i; $j++) $prod *= $arr[$j]; // Store sum of all // the products $sum += $prod; } // Return sum return $sum;} // Driver code $arr = array( 1, 2, 3, 4, 5, 6 ); $n = count($arr); $k = 3; echo calcSOP($arr, $n, $k); // This code is contributed by Sam007?>
Javascript
<script> // Javascript program to find the sum of // product of all subarrays // Function to calculate // the sum of product function calcSOP(arr, n, k) { // Initialize sum = 0 let sum = 0; // Consider every subarray // of size k for (let i = 0; i <= n - k; i++) { let prod = 1; // Calculate product of all // elements of current subarray for (let j = i; j < k + i; j++) prod *= arr[j]; // Store sum of all // the products sum += prod; } // Return sum return sum; } // Driver code let arr = new Array(1, 2, 3, 4, 5, 6); let n = arr.length; let k = 3; document.write(calcSOP(arr, n, k)); // This code is contributed by gfgking </script> |
输出：
210
时间复杂度：O（nk） 一 有效方法 就是使用 滑动窗口 . 1 -考虑第一个子数组/窗口的大小k，做乘积的元素，并添加到总额总和。
for (i=0; i < k; i++) prod = prod * arr[i];
2-现在，通过使用滑动窗口概念，从产品中删除窗口的第一个元素，并将下一个元素添加到窗口中。即
for (i =k ; i < n; i++) { // Removing first element from product prod = prod / arr[i-k]; // Adding current element to the product prod = prod * arr[i]; sum += prod; }
3-回报总额
C++
// C++ program to find the sum of // product of all subarrays #include <iostream> using namespace std; // Method to calculate the sum of product int calcSOP( int arr[], int n, int k) { // Initialize sum = 0 and prod = 1 int sum = 0, prod = 1; // Consider first subarray of size k // Store the products of elements for ( int i = 0; i < k; i++) prod *= arr[i]; // Add the product to the sum sum += prod; // Consider every subarray of size k // Remove first element and add current // element to the window for ( int i = k; i < n; i++) { // Divide by the first element // of previous subarray/ window // and product with the current element prod = (prod / arr[i - k]) * arr[i]; // Add current product to the sum sum += prod; } // Return sum return sum; } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 3; cout << calcSOP(arr, n, k); return 0; } // This code is contributed by avijitmondal1998. |
JAVA
// Java program to find the sum of // product of all subarrays class GFG { // Method to calculate the sum of product static int calcSOP( int arr[], int n, int k) { // Initialize sum = 0 and prod = 1 int sum = 0 , prod = 1 ; // Consider first subarray of size k // Store the products of elements for ( int i = 0 ; i < k; i++) prod *= arr[i]; // Add the product to the sum sum += prod; // Consider every subarray of size k // Remove first element and add current // element to the window for ( int i = k; i < n; i++) { // Divide by the first element // of previous subarray/ window // and product with the current element prod = (prod / arr[i - k]) * arr[i]; // Add current product to the sum sum += prod; } // Return sum return sum; } // Driver method public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 }; int k = 3 ; System.out.println(calcSOP(arr, arr.length, k)); } } |
Python3
# Python3 program to find the sum of # product of all subarrays # Function to calculate the sum of product def calcSOP(arr, n, k): # Initialize sum = 0 and prod = 1 sum = 0 prod = 1 # Consider first subarray of size k # Store the products of elements for i in range (k): prod * = arr[i] # Add the product to the sum sum + = prod # Consider every subarray of size k # Remove first element and add current # element to the window for i in range (k, n, 1 ): # Divide by the first element of # previous subarray/ window and # product with the current element prod = (prod / arr[i - k]) * arr[i] # Add current product to the sum sum + = prod # Return sum return int ( sum ) # Drivers code arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] n = len (arr) k = 3 print (calcSOP(arr, n, k)) # This code is contributed 29AjayKumar |
C#
// C# program to find the sum of // product of all subarrays using System; public class GFG { // Method to calculate the sum of product static int calcSOP( int [] arr, int n, int k) { // Initialize sum = 0 and prod = 1 int sum = 0, prod = 1; // Consider first subarray of size k // Store the products of elements for ( int i = 0; i < k; i++) prod *= arr[i]; // Add the product to the sum sum += prod; // Consider every subarray of size k // Remove first element and add current // element to the window for ( int i = k; i < n; i++) { // Divide by the first element // of previous subarray/ window // and product with the current element prod = (prod / arr[i - k]) * arr[i]; // Add current product to the sum sum += prod; } // Return sum return sum; } // Driver method public static void Main() { int [] arr = { 1, 2, 3, 4, 5, 6 }; int k = 3; // Function calling Console.WriteLine(calcSOP(arr, arr.Length, k)); } } // This code is contributed by Sam007 |
PHP
<?php // php program to find the sum of // product of all subarrays // Function to calculate the sum of product function calcSOP( $arr , $n , $k ) { // Initialize sum = 0 and prod = 1 $sum = 0; $prod = 1; // Consider first subarray of size k // Store the products of elements for ( $i = 0; $i < $k ; $i ++) $prod *= $arr [ $i ]; // Add the product to the sum $sum += $prod ; // Consider every subarray of size k // Remove first element and add current // element to the window for ( $i = $k ; $i < $n ; $i ++) { // Divide by the first element // of previous subarray/ window // and product with the current element $prod = ( $prod / $arr [ $i - $k ]) * $arr [ $i ]; // Add current product to the sum $sum += $prod ; } // Return sum return $sum ; } // Drivers code $arr = array ( 1, 2, 3, 4, 5, 6 ); $n = count ( $arr ); $k = 3; echo calcSOP( $arr , $n , $k ); // This code is contributed by Sam007 ?> |
Javascript
<script> // JavaScript program for the above approach function calcSOP(arr,n,k) { // Initialize sum = 0 and prod = 1 let sum = 0, prod = 1; // Consider first subarray of size k // Store the products of elements for (let i = 0; i < k; i++) prod *= arr[i]; // Add the product to the sum sum += prod; // Consider every subarray of size k // Remove first element and add current // element to the window for (let i = k; i < n; i++) { // Divide by the first element // of previous subarray/ window // and product with the current element prod = (Math.floor(prod / arr[i - k])) * arr[i]; // Add current product to the sum sum += prod; } // Return sum return sum; } // Driver method let arr= [1, 2, 3, 4, 5, 6 ]; let k = 3; document.write(calcSOP(arr, arr.length, k)); // This code is contributed by Potta Lokesh </script> |
输出：
210
时间复杂性： O（n） 本文由 萨希尔·查布拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
