有一串数,只为1或-1,求这个串的子串中所有数的和大于等于0的子串个数,不要使用暴力方法...比如一个4个数的串1,-1,1,-1,子串和大于等于0的个数为7,求省时间的方法1和-1是随机放的,有可能全

Question

有一串数,只为1或-1,求这个串的子串中所有数的和大于等于0的子串个数,不要使用暴力方法...
比如一个4个数的串 1 ,-1,1,-1,子串和大于等于0的个数为7,求省时间的方法
1和-1是随机放的,有可能全是1或全是-1,或者是 1 1 1 1 -1 -1 1 -1 1 1 1 -1之类的..
比如一个数组a[4] a[0]=1,a[1]=-1,a[2]=1,a[3]=-1,这个数组的连续字串之和大于0的个数为7.分别是 a[0],a[2],a[0] a[1],a[1] a[2],a[0] a[1] a[2] a[3],a[2] a[3].a[0] a[1] a[2] 子串要求是连续的.这个要用树状数组来解才能省时间...

Answer 1

n=1时,a1=1
n=2时,a2=3
n=3时,a3=4
n=4时,a4=12
n=5时,a5=16
……
n为奇数时,an=2^(n-1)
n为偶数时,an=3X2^(n-2)
楼主在题中所说的比如一个4个数的串 1 ,-1,1,-1,子串和大于等于0的个数为7,这个结论是错的,你可以排一下,不是7,而是12.