查找具有负乘法的数组子序列

Question

我正在尝试构建一个算法，该算法为我提供了 个具有其元素负积的子序列.

例如：

[-1, 2, -3] 的答案是 4。 ([-1] [-3] [-1, 2] 和 [2, -3])

Answer 1

一种令人头疼的方法是记忆。您可以定义一个记忆函数 count_neg_seq_at(i)，它 returns 从索引 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

查找具有负乘法的数组子序列

Find sub sequence of array that have negative multiplication

arrays

algorithm

recursion

subsequence