找到一个数组所有子数组中所有元素的乘积

Question

我有一个包含n个元素的数组A，想要找出数组A中所有可能子数组中元素的乘积。我希望通过DP实现解决方案，并将所有乘积值存储在数组B中。作为编程新手，我进行了大量的谷歌搜索，但未能找到我的问题的确切解决方案。有人能帮助我提供这个问题的逻辑吗？ 例如：

A={1,2,3}

所有可能的子数组为：

{{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

所以所有可能的产品都是

{1,2,3,2,3,6,6} 

分别。希望能得到帮助，谢谢。

- vivek sehgal

---

@YoungHobbit，实际上我不知道如何解决这个对于大的n的问题，但是我在谷歌上搜索了一些链接，但是我没有理解。 - vivek sehgal

你应该考虑使用正确的术语：子序列，而不是子数组。子数组是数组的连续部分。 - Tanishq Vyas

Answer 1

这可能会有所帮助：

在每个实例中，您必须做出两个选择：

要么选择当前子数组中的数组元素，要么不选择。以下递归可能会有所帮助：

f(i,p)=f(i+1,p*arr[i])||f(i+1,p)

- RKS10222

Answer 2

你可能知道如何创建数组的所有子数组，因此这使问题变得容易：

如果你的array(a)中有n个元素，并且其中一个元素是m，那么为了计算你的问题，你可以使用以下方法：

MySubArray(a , n) = new array{ MySubArray(a - {m} , n - 1) , MySubArray(a - {m} , n - 1) * m};

这意味着你需要对a - {m}的所有子数组计算一次问题，然后再将m添加到所有子数组中并将它们的乘积乘以m。

- Zhr Saghaie

Answer 3

对于大小为M的集合（包括空集），有N = 2^M-1个子集，因此每个子集对应于范围内的数字0..N-1。 如果某个数字中设置了第k位，则第k个元素在相应的子集中呈现。

动态规划方法允许重复使用计算出的乘积，因此复杂度相对于输出大小是线性的O(N) = O(2^M)
Delphi代码：

var
  A, Prods: TArray<Integer>;
  iA, i, SeriesLen, N: Integer;
  s: String;
begin
  A := TArray<Integer>.Create(2, 3, 5, 7);
  N := 1 shl Length(A); //output array size = 2^InputLength

  SetLength(Prods, N);
  Prods[0] := 1;
  SeriesLen := 1;
  for iA := 0 to Length(A) - 1 do begin
    for i := 0 to SeriesLen - 1 do
      Prods[i + SeriesLen] := Prods[i] * A[iA];
    SeriesLen := SeriesLen * 2;
  end;

output Prods[1]..Prods[N-1]

Result: 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210 

- MBo

Answer 4

一个提示是让你自己尝试一下，考虑到我们在一个数组中有N个元素。这些元素可能是唯一的，也可能不是唯一的。然后我们创建一个二进制数字的列表/数组来映射所有可能的子数组（虽然根据你的疑问，正确的术语应该是子序列）。

For example : 
here N = 4.
Array : 1 2 3 2

The possible sub sequences would be

Binary Encoding (1 to include, 0 to exclude) :
0 0 0 0 : {}     # No use for us in this case
0 0 0 1 : {2}
0 0 1 0 : {3}
0 0 1 1 : {3, 2}
0 1 0 0 : {2}
0 1 0 1 : {2,2}
0 1 1 0 : {2,3}
0 1 1 1 : {2,3,2}
1 0 0 0 : {1}
1 0 0 1 : {1,2}
1 0 1 0 : {1,3}
1 0 1 1 : {1,3,2}
1 1 0 0 : {1,2}
1 1 0 1 : {1,2,2}
1 1 1 0 : {1,2,3}
1 1 1 1 : {1,2,3,2}


Thus you can generate all the sub sequences for a given array. and find their product.

- Tanishq Vyas