#1567

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Length of Subarray With Positive Product

Given an array, find the maximum length of a subarray with a positive product using dynamic programming.

Problem Statement

Given an array of integers, you need to determine the maximum length of a subarray where the product of its elements is positive.

You can assume that the subarray cannot contain zero, as it would cause the product to become zero. You should return the maximum possible length of a subarray with a positive product.

Examples

Example 1

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

Output: 4

The array nums already has a positive product of 24.

Example 2

Input: nums = [0,1,-2,-3,-4]

Output: 3

The longest subarray with positive product is [1,-2,-3] which has a product of 6. Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3

Input: nums = [-1,-2,-3,0,1]

Output: 2

The longest subarray with positive product is [-1,-2] or [-2,-3].

Constraints

1 <= nums.length <= 105
-109 <= nums[i] <= 109

Solution Approach

State Transition Dynamic Programming

Track the lengths of subarrays with positive and negative products. Split the array into segments by zeroes, and for each segment, use dynamic programming to calculate the maximum length of a subarray with a positive product.

Handling Negative Numbers

Negative numbers flip the product's sign, so if there are two negative numbers, the product becomes positive. Keep track of the first negative number and its index to help in transitioning the state for subsequent elements.

Greedy Subarray Split by Zero

Split the array into smaller subarrays based on zeroes. A subarray with a product of zero cannot contribute to the result, so treat each segment independently and find the longest positive-product subarray in each segment.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of elements in the array, but for each subarray segment, we only iterate once. Thus, the overall time complexity is O(n), where n is the length of the array. Space complexity depends on how the states (positive/negative product lengths) are stored, which can be O(1) or O(n) depending on the approach used.

What Interviewers Usually Probe

Look for a solution that can split the array by zeroes and uses dynamic programming to keep track of the lengths of positive subarrays.
Check if the candidate handles negative numbers and updates the product state accordingly.
The candidate should be able to distinguish between the greedy approach for splitting the array and dynamic programming for tracking subarray lengths.

Common Pitfalls or Variants

Common pitfalls

Failing to handle zeroes correctly, treating them as part of subarrays.
Incorrectly updating the state for negative numbers, leading to wrong subarray length calculations.
Not splitting the array at zeroes, which results in incorrect handling of subarrays that contain zeroes.

Follow-up variants

Implementing the solution without using dynamic programming, focusing only on greedy subarray splitting.
Modifying the approach to return the subarray itself, not just the length.
Optimizing the space complexity to O(1) by avoiding extra storage for the state.

FAQ

How do I handle zeroes in the array?

Zeroes divide the array into smaller subarrays. Any subarray containing zeroes cannot contribute to the product, so treat each segment between zeroes as an independent subarray.

What is the state transition dynamic programming pattern?

State transition dynamic programming helps track two states for each subarray: the length of the subarray with a positive product and the length with a negative product.

How does the negative number handling affect the product?

When two negative numbers are encountered, the product flips from negative to positive. This is why it's important to track negative product lengths and update them accordingly.

Can this problem be solved without dynamic programming?

It can be solved using a greedy approach by simply splitting the array by zeroes and calculating the subarray lengths manually, but dynamic programming makes it more efficient.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the array, as we iterate through the array once and use constant-time operations for each element.

terminal

Solution

Solution 1: Dynamic Programming

We define two arrays $f$ and $g$ of length $n$, where $f[i]$ represents the length of the longest subarray ending at $\textit{nums}[i]$ with a positive product, and $g[i]$ represents the length of the longest subarray ending at $\textit{nums}[i]$ with a negative product.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Solution 2: Dynamic Programming (Space Optimization)

We observe that for each $i$, the values of $f[i]$ and $g[i]$ only depend on $f[i - 1]$ and $g[i - 1]$. Therefore, we can use two variables $f$ and $g$ to record the values of $f[i - 1]$ and $g[i - 1]$, respectively, thus optimizing the space complexity to $O(1)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Continue Practicing

#1578 minimum time to make rope colorful #1537 get the maximum score #1526 minimum number of increments on subarrays to form a target array