Reputation: 21
I'm trying to build an algorithm that given me count of subsequence that have a negative product of their elements.
For example:
Answer for [-1, 2, -3]
is 4
. ([-1]
[-3]
[-1, 2]
and [2, -3]
)
Upvotes: 0
Views: 289
Reputation: 80285
Linear algorithm (takes zeros into account).
At i-th step res
is incremented by the number of negative-product subsequences ending in i-th position.
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
Upvotes: 0
Reputation: 11602
A headache-proof way is to go with memoization. You can define a memoized function count_neg_seq_at(i)
that returns the count of all negative subsequences starting at indexi
. The function count_neq_seq_at(i)
can be defined recursively in terms of count_neg_seq_at(i+1)
. The final answer is given by something like sum(count_neg_seq_at(i) for i = 1:n)
where n
is the length of the array.
Here is a Python implementation:
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
Upvotes: 1