题解 | #乘积为正数的最长连续子数组#

思路

我们可以设置初始条件，即ans=0, neg_num=0（表示遇到几个负数），再设置一个栈stack存放ans。考虑如下几种情况

• 当遇到正数时，直接让ans自增1
• 当遇到0的时候，则重置所有初始条件
• 当遇到负数的时候，分两类来考虑：
  • 如果此时neg_num为0，则说明之前累计乘积都没有负数，让neg_num自增1，并把当前的值ans添加到stack中。
  • 如果此时neg_num为1，则说明之前累计乘积为负，此时即将变正，那么我们只需要把之前存入栈中的值取出（即代表上一次遇到负数时，之前累计乘积为正时的ans），并让$ans=pr{e}_{ans}+ans+2ans\; =\; pre\_\{ans\}\; +\; ans\; +\; 2$，其中ans表示从第一个负数到第二个负数之间累计的正数个数，2表示两个neg_num，再把neg_num置位0.

当全部遍历结束后，还需要把ans入栈，然后比较栈中所有ans，返回其中最大值。

JavaScript代码实现

let n = ~~readline()
let arr = readline().split(' ').map(x => parseInt(x))

function main(arr, n) {
    if(n === 1) return arr[0] > 0 ? 1 : 0
    let ans_arr = [], ans = 0
    let neg_num = 0
    for(let i = 0 ; i < n ; i++) {
        let x = arr[i]
        if(x === 0) {
            ans_arr.push(ans)
            neg_num = 0
            ans = 0
            continue 
        }
        // 如果为正数
        if(x > 0) {
            ans++
        }else {
            // 负数时，neg_num++，并把ans加入数组
            // 如果neg_num为2的时候，则把ans_arr最后一项取出，加上当前的ans，再加上2
            neg_num++
            if(neg_num % 2 === 1) {
                ans_arr.push(ans)
                ans = 0
            }else {
                let pre = ans_arr.pop()
                ans = pre + ans + 2
                neg_num = 0
            }
        }
    }
    ans_arr.push(ans)
    return Math.max(...ans_arr)
}

console.log(main(arr, n))