Maximum Length of Subarray With Positive Product — LeetCode 1567 Python Solution

The problem

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive. A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Example

Input

nums = [1,-2,-3,4]

Output

4

Explanation

The array nums already has a positive product of 24.

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1567. Maximum Length of Subarray With Positive Product is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems