How to count all contiguous subsequences with positive sum?
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 &lt; i_2$ such that $B_{i_1} &lt; 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$.