【BD算法题】长度为n的数组的所有乘积为正的连续子数组个数、所有乘积为负的连续子数组个数

Problem

魔法师小树有n个魔法元素，他把它们排成一行，从左到右第i个魔法元素的能量值是一个非零整数 a i a_i ai​。小树每次施展魔法的方式是挑选一段连续的非空的魔法元素，将它们的能量乘起来，得到的值就是这次魔法的总能量。如果能量大于零即为白魔法，否则为黑魔法。

现在想知道施展一个白魔法或黑魔法的方案数分别有多少？两个方案不同是指挑选的连续区间不同。
描述：
第一行有一个整数n（1<n<2*10^5），表示魔法元素的个数。
第二行有n个整数 a 1 , a 2 , a 3 , . . . , a n ( − 1 0 9 < = a i < = 1 0 9 ; a i ≠ 0 ) a_1, a_2, a_3, ..., a_n (-10^9<=a_i<=10^9; a_i \neq 0) a1​,a2​,a3​,...,an​(−109<=ai​<=109;ai​=0) 代表魔法元素的能量值。
输出描述：
输出两个整数，分别表示施展一个白魔法和施展一个黑魔法的方案数。

示例输入：

5
5 -3 3 -1 1

示例输出：

7 8

题目简化

题目比较长，简单来说，就是求长度为n的数组的所有乘积为正的连续子数组个数、所有乘积为负的连续子数组个数，其中数组中不含0. 与动态规划的经典问题乘积最大子数组不同，本题要找出所有情况，最简单直接的想法是两层for循环，暴力检索。

暴力法

两层for循环，i 为左指针， j 为右指针。注意长度为 1 的子数组的处理。

def problem2(arr):
    n = len(arr)
    poss = 0
    neg = 0
    for i in range(n):
        tmp=arr[i]
        if tmp>0:
            poss+=1
        else:
            neg +=1
        for j in range(i+1,n):
            tmp*=arr[j]
            if tmp>0:
                poss+=1
            else:
                neg +=1
    return poss, neg

连续子数组个数总和为 1 + 2 + 3 + . . . + n = n ∗ ( n + 1 ) / 2 1+2+3+...+n = n*(n+1)/2 1+2+3+...+n=n∗(n+1)/2， 所以时间复杂度为 O ( n 2 ) O(n^2) O(n2).
考虑到当数组中元素很大时，乘法可能耗时，可以先遍历一遍，只保存数组中元素的符号，以替代原数组。
然而，此方法的复杂度依旧很高，在n很大时无法快速求解。

由位置 i 推断位置 j

示例 递推求解 乘积为正连续子数组个数，乘积为负的子数组个数可以由 n ( n + 1 ) / 2 − 乘积为正的子数组个数 n(n+1)/2 - 乘积为正的子数组个数 n(n+1)/2−乘积为正的子数组个数 求出。

如果已知数组 a [ 1 : i ] a[1:i] a[1:i]的乘积为正连续子数组个数，要计算数组 a [ 1 : i + 1 ] a[1:i+1] a[1:i+1]的乘积为正连续子数组个数，可以拆分为
1、 a [ 1 : i ] a[1:i] a[1:i]的乘积为正连续子数组个数
2、 a [ 1 : i + 1 ] , a [ 2 : i + 1 ] , a [ 3 : i + 1 ] , . . . , a [ i : i + 1 ] , a [ i + 1 ] a[1:i+1], a[2:i+1], a[3:i+1] ,... , a[i:i+1], a[i+1] a[1:i+1],a[2:i+1],a[3:i+1],...,a[i:i+1],a[i+1]中乘积为正的个数。

要快速判断 a [ 1 : i + 1 ] , a [ 2 : i + 1 ] , a [ 3 : i + 1 ] , . . . , a [ i : i + 1 ] , a [ i + 1 ] a[1:i+1], a[2:i+1], a[3:i+1] ,... , a[i:i+1], a[i+1] a[1:i+1],a[2:i+1],a[3:i+1],...,a[i:i+1],a[i+1] 乘积的符号，可以考虑用一个数组signs存下 a [ 1 ] ∗ a [ 2 ] ∗ . . . ∗ a [ i ] = a [ i ] ! a[1]*a[2]*...*a[i] = a[i]! a[1]∗a[2]∗...∗a[i]=a[i]!的符号（只需要遍历一次数组即可得到 O ( n ) O(n) O(n)）。 a [ j : i ] a[j: i] a[j:i]的累乘符号，可以由 a [ j ] ! a[j]! a[j]!与 a [ i ] ! a[i]! a[i]!的符号确定。因此，a[1:i+1], a[2:i+1], a[3:i+1] ,... , a[i:i+1], a[i+1]中乘积为正的个数，可以由累积符号确定：

1、如果 a [ i + 1 ] a[i+1] a[i+1]为正，比如由上表中4到7，增加的情况有： + − + − + +-+-+ +−+−+ , − + − + -+-+ −+−+, + + + 三种，即signs[:i+1]中1的个数。
2、如果 a [ i + 1 ] a[i+1] a[i+1]为负，比如由上表中16到18，增加的情况有： + − + + + − +-+++- +−+++−, − + + + − -+++- −+++− 两种， 即sign[:i] 中0的个数。

由此写出代码：

def problem2_spped2(arr):
    '''
    signs: arr[i]! 的符号, 1正，0负
    poss_list: 到位置i的所有 乘积为正的 连续子数组个数
    ones, zeros: 记录signs几个0，几个1
    '''
    n=len(arr)
    tmp_sign = arr[0]
    poss = int(arr[0]==(abs(arr[0])))
    poss_list=[poss]
    signs = [poss]
    ones = int(poss==1)
    zeros = int(poss!=1)
    
    for i in range(1,len(arr)):
        tmp_sign *= arr[i]
        if tmp_sign<0:
            signs.append(0)
            zeros+=1
        else:
            signs.append(1)
            ones+=1
        
        if signs[i]==0:
            poss += zeros-1
        else:
            poss+= ones
        poss_list.append(poss)
    return poss, (n*(n+1))//2-poss

测试

if __name__ =='__main__':
    import time
    import numpy as np
    
    arr=[1,-2,3,-4,5, 6, 7, -8,-9,-10]
    t1 = time.time()
    print(problem2(arr))
    t2 = time.time()
    print(t2-t1)
    print(problem2_spped2(arr))
    t3 = time.time()
    print(t3-t2)

    arr = np.random.randn(1,2*10**5).tolist()[0]
    t2 = time.time()
    print(problem2_spped2(arr))
    t3 = time.time()
    print(t3-t2)

可以看到，两种方法结果一直，优化后的方法在处理 n = 2 ∗ 1 0 5 n=2*10^5 n=2∗105 也只需要0.05秒。