# How to count all contiguous subsequences with positive sum?

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?

• 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. – D.W. Oct 20 '17 at 14:46
• @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)$ – Franz Wexler Oct 20 '17 at 18:24

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$.