2
$\begingroup$

I have array $t$ with size $n \leq 10^6$. It has only two kinds of elements inside: $1$ or $-1$. I need to count how many contiguous subsequences have positive sum.

This pseudocode demonstrates exactly the behavior I want, but is too slow for large $n$:

c = 0
for i = 1 to n do
    for i = j to n do
       if sum(u[i:j]) > 0 then
           c = c + 1
return c

Partial sums can be used to optimize it, but it will still be $O(n^2)$.

Here are some examples if they help:

[-1, 1, -1, -1, -1] $\rightarrow$ 1

[1, -1, 1, 1, -1, 1] $\rightarrow$ 14

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1] $\rightarrow$ 55

Does there exist linear or $n \log n$ solution?

$\endgroup$
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving practice/contest-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Oct 20 '17 at 14:46
  • $\begingroup$ @D.W. Actually I think I understand the concepts very well. I just wanted to practice and honestly don't have any idea how to solve this problem I encountered. I tried many solutions, but I got stuck because they had too big time complexity and the best I got was $O(n^2)$ $\endgroup$ – Franz Wexler Oct 20 '17 at 18:24
1
$\begingroup$

Given the array $A_1,\ldots,A_n$, start by computing $B_i = \sum_{j \leq i} A_j$. You want to count the number of pairs $i_1 < i_2$ such that $B_{i_1} < B_{i_2}$, where $0 \leq i_1,i_2 \leq n$. Each such pair corresponds to a a contiguous subsequence $A_{i_1+1},\ldots,A_{i_2}$ whose sum is positive. This is the same as the classical problem of counting the number of inversions in an array (this is what you get if you reverse $B$), which can be solved in $O(n\log n)$.

It is plausible that you can do better in your case since the numbers are $\pm 1$.

$\endgroup$
  • $\begingroup$ Very similar to what I attempted, but actually works! Thanks! $\endgroup$ – Franz Wexler Oct 20 '17 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.