长度为k的所有子阵列元素的产品总和 [英] Sum of products of elements of all subarrays of length k

问题描述

长度的数组的 N 给出。找到的子阵列的元件的乘积之和

An array of length n is given. Find the sum of products of elements of the sub-array.

说明

阵列 A = [2，3，4] 长度 3

子数组的长度 2 = [2,3]，[3,4]，[2,4]

Sub-array of length 2 = [2,3], [3,4], [2,4]

在元素的产品的 [2，3] = 6

Product of elements in [2, 3] = 6

在元素的产品的 [3，4] = 12

Product of elements in [3, 4] = 12

在元素的产品的 [2,4] = 8

Product of elements in [2, 4] = 8

总和为长度的子阵 2 = 6 + 12 + 8 = 26

Sum for subarray of length 2 = 6+12+8 = 26

同样，对于长度 3 ，和= 24

Similarly, for length 3, Sum = 24

由于，产品可以为子阵列更高的长度更大的计算模 1000000007

As, products can be larger for higher lengths of sub-arrays calculate in modulo 1000000007.

什么是有效的方法找到这些款项的所有可能的长度子阵列，即，1，2，3，...，n，其中的 N 是数组的长度。

What is an efficient way for finding these sums for subarrays of all possible lengths, i.e., 1, 2, 3, ......, n where n is the length of the array.

推荐答案

我们首先创建一个递推关系。让 F（N，K）是长度 K 子阵列的所有产品从一个数组的总和 A 长度 N 。基本情况是简单的：

We first create a recursive relation. Let f(n, k) be the sum of all products of sub-arrays of length k from an array a of length n. The base cases are simple:

f(0, k) = 0 for all k
f(n, 0) = 1 for all n

第二条规则似乎有点违反直觉，但1是乘法的零元素。

The second rule might seem a little counter-intuitive, but 1 is the zero-element of multiplication.

现在我们发现了一个递推关系为 F（N + 1，K）。我们希望大小 K 的所有子阵列的产品。有两种类型的子阵列在这里：那些包括 A [N + 1] 和那些不包括 A [N + 1] 。对那些不包括总和 A [N + 1] 完全 F（N，K）。那些包括 A [N + 1] 是完全长度的所有子阵 K-1 与一[N + 1] 添加，所以他们总结出的产品是 A [N + 1] * F（N，K-1）。

Now we find a recursive relation for f(n+1, k). We want the product of all subarrays of size k. There are two types of subarrays here: the ones including a[n+1] and the ones not including a[n+1]. The sum of the ones not including a[n+1] is exactly f(n, k). The ones including a[n+1] are exactly all subarrays of length k-1 with a[n+1] added, so their summed product is a[n+1] * f(n, k-1).

这完成了我们的递推关系：

This completes our recurrence relation:

f(n, k) = 0                               if n = 0
        = 1                               if k = 0
        = f(n-1, k) + a[n] * f(n-1, k-1)  otherwise

---

您可以用一个巧妙的利用非常有限的内存为您的动态规划，因为功能 F 只依赖于两个以前的值：

---

You can use a neat trick to use very limited memory for your dynamic programming, because function f only depends on two earlier values:

int[] compute(int[] a) {
    int N = a.length;
    int[] f = int[N];
    f[0] = 1;

    for (int n = 1; n < N; n++) {
        for (int k = n; k >= 1; k--) {
            f[k] = (f[k] + a[n] * f[k-1]) % 1000000007;
        }
    }

    return f;
}

这篇关于长度为k的所有子阵列元素的产品总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！