arrays - 如何在线性时间内找到数组中所有可能子数组的乘积？

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) 复杂度中找到？谢谢！

标签： arraysdynamic-programmingnumber-theory

Answer 1

不，这是不可能的，因为结果的大小是二次的（特别是 n(n+1)/2）。仅仅写出结果的每一个条目就已经花费了二次时间，不管计算它有多容易。