Sum of products of elements of all subarrays of le

问题:

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

Explanation

Array A = [2, 3, 4] of length 3.

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

Product of elements in [2, 3] = 6

Product of elements in [3, 4] = 12

Product of elements in [2, 4] = 8

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

Similarly, for length 3, Sum = 24

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

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.

回答1:

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

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

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

---

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;
}

回答2:

There is rather simple way:
Construct product of terms (1 + A[i] * x):

P = (1 + A[0] * x) * (1 + A[1] * x) * (1 + A[2] * x)...*(1 + A[n-1] * x)

If we open the brackets, then we'll get polynomial

P = 1 + B[1] * x + B[2] * x^2 + ... + B[n] * x^n

Kth coefficient, B[k], is equal to the sum of products of sets with length K - for example, B[n] = A[0]*A[1]*A[2]*..A[n-1], B[2] = A[0]*A[1] + A[0]*A[2] + ... + A[n-2]*A[n-1] and so on.

So to find sum of products of all possible sets, we have to find value of polynomial P for x = 1, then subtract 1 to remove leading 0th term. If we don't want to take into consideration single-element sets, then subtract B1 = sum of A[i].

Example:

(1+2)(1+3)(1+4) = 60
60 - 1 = 59
59 - (2 + 3 + 4) = 50 = 24 + 26 - as your example shows