Найти подпоследовательность массива с отрицательным умножением

Question

Я пытаюсь построить алгоритм , который дал бы мне подсчет подпоследовательности, у которой отрицательное произведение их элементов .

Например:

Ответ для [-1, 2, -3] - 4. ([-1] [-3] [-1, 2] и [2, -3])

Answer 1

Способ защиты от головной боли - go с напоминанием. Вы можете определить запомненную функцию count_neg_seq_at(i), которая возвращает количество всех отрицательных подпоследовательностей, начиная с индекса i. Функция count_neq_seq_at(i) может быть определена рекурсивно в терминах count_neg_seq_at(i+1). Окончательный ответ задается чем-то вроде sum(count_neg_seq_at(i) for i = 1:n), где n - длина массива.

Вот реализация Python:

from functools import lru_cache
import numpy as np

np.random.seed(0)
arr = np.random.randint(-10, 10, 100)

# naive benchmark for checking correctness
from itertools import  combinations

def naive(xs):
  n = len(xs)
  count_neg = 0
  for i, j in combinations(range(n+1), 2):
    count_neg += sum(x < 0 for x in xs[i:j]) % 2
  return count_neg

# memoized approach
def count_negative_subseq(arr):
  neg = (arr < 0).astype(int)
  n = len(arr)
  # make a memoized function for counting negative subsequences
  # starting at a given index
  @lru_cache(None)
  def negative_starting_at(i):
    'number of subseqs with negative product starting at i'
    if i == n - 1:
      # base case: return one if the last element of the array is negative
      return neg[i]
    elif neg[i]:
      # if arr[i] is negative, return the count of positive product subsequences
      # from i+1 to n, plus one
      return n - i - negative_starting_at(i+1)
    else:
      # if arr[i] is positive, return count of negative product subsequences
      # from i+1 to n
      return negative_starting_at(i+1)

  # return sum of negative subsequences at each point
  return sum(negative_starting_at(i) for i in range(n))

print(naive(arr))
print(count_negative_subseq(arr))

# 2548
# 2548

Answer 2

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

def cntneg(a):
    negcnt = 0
    poscnt = 1
    mul = 1
    res = 0
    for i in range(len(a)):
        if a[i]== 0:
            negcnt = 0
            poscnt = 1
            mul = 1
        else:
            if a[i] < 0:
                mul = - mul
            if mul > 0:
                res += negcnt
                poscnt += 1
            else:
                res += poscnt
                negcnt += 1
    return res

print(cntneg([-1, 2, -3, 4, -5, 0, -1, 2, 2, -3]))
>>15