如何在线性时间内找到阵列中所有可能的子阵列的乘积？

Question

假设我有一个数组A [4] = {5,6,2,4}

子数组是：{{5}，{6}，{2}，{4}，{5、6}，{6、2}，{2、4}，{5、6、2} ，{6，2，4}，{5，6，2，4}}

我需要包含每个子数组乘积的数组作为输出，即{5，6，2，4，30，12，8，60，48，240}

这是我的O（n ^ 2）方法：

const int a = 4;
const int b = 10; //n(n+1)/2
int arr[a] = {5, 6, 2, 4};
int ans[b] = {0};
int x = 0;
for(int i = 0; i < n; i++) {
  prod = 1;
  for(int j = i; j < n; j++) {
    prod *= arr[j];
    ans[x++] = prod;
  }
}

//ans is the o/p array

我想知道是否可以以O（n）的复杂度找到它？谢谢！

Answer 1

不，这是不可能的，因为结果的大小是平方的（特别是n（n + 1）/ 2）。不管结果多么容易，仅写入结果的每个条目都将花费二次时间。