Как найти произведение всех возможных подмассивов в массиве за линейное время?

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

Нет, это невозможно, потому что размер результата равен квадратичному c (особенно n (n + 1) / 2). Простое написание каждой записи результата уже стоит квадратичного c времени, независимо от того, насколько легко его вычислить.