Подсчитать общее количество подмассивов с отрицательным продуктом в O (n)

Question

В массиве, состоящем из целого числа (отрицательное, положительное и нулевое)
задача состоит в том, чтобы найти Общее количество подмассивов , чье произведение равно Отрицательное .

Если я найду все подмассивы, а затем проверим наличие отрицательного продукта, он перейдет в O (n ^ 2) . </p> <pre>long long n,a[200001],i,neg[200001],j; long long totalneg=0; //prefix array to store number of negative element cin>>n; a[0]=0,neg[0]=0; for(i=1;i<=n;i++) { cin>>a[i]; if(a[i]<0) neg[i]=neg[i-1]+1; else neg[i]=neg[i-1]; } for(i=1;i<=n;i++) { for(j=i;j<=n;j++) { if( (neg[j]-neg[i-1]) %2 !=0 ) totalneg++; } } cout<<totalneg;

Так, как я могу найти это в O (n) время.

Answer 1

Начиная с первого значения: если оно отрицательное, вы нашли один из этих подмассивов, если оно положительное, вы нашли один подмассив с положительной суммой (приходящий к нулю позже).

Затем давайте рассмотрим следующийзначение: если отрицательное / положительное значение, вы нашли еще один такой подмассив. Однако вы можете комбинировать их со всеми найденными вами подмассивами!

Если вы нашли n _p положительных подмассивов, вы получите еще один n _p положительные подмассивы, если текущее значение положительно, или другие n _p отрицательные массивы, если текущее значение отрицательно, аналогично для числа отрицательных n _n массивов, просто вы получаете новые массивы с отрицательным произведением для положительного значения и новые массивы с положительным произведением для отрицательного значения.

Специальное значение ноль: это значениесодержащийся в любом подмассиве будет давать ноль как продукт, больше не имеет значения, каковы другие факторы. Таким образом, вы можете остановиться на этом этапе, добавив n _n к некоторому общему количеству и перезапустить с n _p и n _n , равное нулю.

Рассмотрев все числа в массиве, не забудьте добавить последние вычисленные n _n к общей сумме.

Теперь все, что осталось, это подделать этот алгоритм в код, который остается на ваше усмотрение ... Если у вас возникнут проблемы с этим, не стесняйтесь задавать новый вопрос, предоставляякод, который вы написали до сих пор.