文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡(jiǎn)書

1. Description

Maximum Length of Subarray With Positive Product

2. Solution

解析：Version 1，首先要將數(shù)組從所有零處斷開，這樣可以保證乘積一定不為0，采用pre來表示前一個(gè)0所在的位置，初始狀態(tài)為-1，當(dāng)碰到一個(gè)0時(shí)，計(jì)算不包括0在內(nèi)的子數(shù)組長(zhǎng)度m，如果m > 0，說明子數(shù)組不為空。要計(jì)算子數(shù)組的乘積為正數(shù)的最長(zhǎng)長(zhǎng)度，需要統(tǒng)計(jì)數(shù)組中負(fù)數(shù)的個(gè)數(shù)neg，如果為偶數(shù)，則最長(zhǎng)長(zhǎng)度為子數(shù)組長(zhǎng)度，如果為奇數(shù)，則長(zhǎng)度應(yīng)為子數(shù)組長(zhǎng)度減去包含第一個(gè)負(fù)數(shù)在內(nèi)的前一部分長(zhǎng)度或者是從子數(shù)組開始到最后一個(gè)負(fù)數(shù)之前的長(zhǎng)度中較大的一個(gè)。分別用start，end來表示第一個(gè)負(fù)數(shù)和最后一個(gè)負(fù)數(shù)的位置。遍歷數(shù)組后，如果最后一個(gè)數(shù)不為0，要計(jì)算最后一個(gè)子數(shù)組。Version 2為了保證計(jì)算最后一個(gè)子數(shù)組，在nums數(shù)組后加了一個(gè)0。Version 3使用動(dòng)態(tài)規(guī)劃解決，pos[i]和neg[i]分別表示以i為結(jié)尾的乘積為正數(shù)的最長(zhǎng)子數(shù)組長(zhǎng)度和表示乘積為負(fù)數(shù)的最長(zhǎng)子數(shù)組長(zhǎng)度，碰到0時(shí)重新統(tǒng)計(jì)。根據(jù)nums[i]的值可以分為三種情況，nums[i] = 0，此時(shí)pos[i]和neg[i]都為0；nums[i] > 0時(shí)，pos[i] = pos[i-1] + 1，如果neg[i-1]為0，則不更新neg[i]，否則，neg[i] = neg[i-1] + 1；nums[i] < 0時(shí)，neg[i] = pos[i-1] + 1，如果neg[i-1]為0，則不更新pos[i]，否則，pos[i] = neg[i-1] + 1，每次更新兩個(gè)數(shù)組之后，要更新最大長(zhǎng)度maximum = max(maximum, pos[i])。

• Version 1

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        maximum = 0
        pre = -1
        neg = 0
        start = -1
        end = -1
        for i in range(n):
            if nums[i] == 0:
                m = i - pre - 1
                if m > 0:
                    if neg % 2 == 0:
                        maximum = max(maximum, m)
                    else:
                        maximum = max(maximum, i - start - 1, end - pre - 1)
                pre = i
                start = -1
                end = -1
                neg = 0
            elif nums[i] < 0:
                neg += 1
                if start == -1:
                    start = i
                end = i
        if pre != n - 1:
            m = n - pre - 1
            if m > 0:
                if neg % 2 == 0:
                    maximum = max(maximum, m)
                else:
                    maximum = max(maximum, n - start - 1, end - pre -1)
        return maximum

• Version 2

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        nums.append(0)
        n = len(nums)
        maximum = 0
        pre = -1
        neg = 0
        start = -1
        end = -1
        for i in range(n):
            if nums[i] == 0:
                m = i - pre - 1
                if m > 0:
                    if neg % 2 == 0:
                        maximum = max(maximum, m)
                    else:
                        maximum = max(maximum, i - start - 1, end - pre - 1)
                pre = i
                start = -1
                end = -1
                neg = 0
            elif nums[i] < 0:
                neg += 1
                if start == -1:
                    start = i
                end = i
        return maximum

• Version 3

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        pos = [0] * n
        neg = [0] * n
        if nums[0] > 0:
            pos[0] = 1
        if nums[0] < 0:
            neg[0] = 1
        maximum = pos[0]
        for i in range(1, n):
            if nums[i] > 0:
                pos[i] = pos[i-1] + 1
                if neg[i-1] != 0:
                    neg[i] = neg[i-1] + 1
            elif nums[i] < 0:
                if neg[i-1] != 0:
                    pos[i] = neg[i-1] + 1
                neg[i] = pos[i-1] + 1
            else:
                pos[i] = 0
                neg[i] = 0
            maximum = max(maximum, pos[i])
        return maximum

Reference

1. https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/