Skip to content

1567. Maximum Length of Subarray With Positive Product

Description

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.

Return the maximum length of a subarray with positive product.

 

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.

Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: 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
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

 

Constraints:

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

Solutions

Solution 1: Dynamic Programming

Thinking

Find the longest subarray whose product is positive. \(n\le 10^5\), so checking every pair overflows and times out. Zeros split the array and a minus only flips the sign, so we may store, at each end, the longest positive and negative products.

Let \(f[i]\) and \(g[i]\) be those two lengths ending at \(i\). A positive value keeps the previous signs; a negative value swaps them; a zero breaks both. The answer is the maximum \(f[i]\).

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.

Initially, if \(\textit{nums}[0] > 0\), then \(f[0] = 1\), otherwise \(f[0] = 0\); if \(\textit{nums}[0] < 0\), then \(g[0] = 1\), otherwise \(g[0] = 0\). We initialize the answer \(ans = f[0]\).

Next, we iterate through the array \(\textit{nums}\) starting from \(i = 1\). For each \(i\), we have the following cases:

  • If \(\textit{nums}[i] > 0\), then \(f[i]\) can be transferred from \(f[i - 1]\), i.e., \(f[i] = f[i - 1] + 1\), and the value of \(g[i]\) depends on whether \(g[i - 1]\) is \(0\). If \(g[i - 1] = 0\), then \(g[i] = 0\), otherwise \(g[i] = g[i - 1] + 1\);
  • If \(\textit{nums}[i] < 0\), then the value of \(f[i]\) depends on whether \(g[i - 1]\) is \(0\). If \(g[i - 1] = 0\), then \(f[i] = 0\), otherwise \(f[i] = g[i - 1] + 1\), and \(g[i]\) can be transferred from \(f[i - 1]\), i.e., \(g[i] = f[i - 1] + 1\).
  • Then, we update the answer \(ans = \max(ans, f[i])\).

After the iteration, we return the answer \(ans\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(\textit{nums}\).

 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = nums[0] > 0 ? 1 : 0;
        g[0] = nums[0] < 0 ? 1 : 0;
        int ans = f[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > 0) {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] > 0 ? g[i - 1] + 1 : 0;
            } else if (nums[i] < 0) {
                f[i] = g[i - 1] > 0 ? g[i - 1] + 1 : 0;
                g[i] = f[i - 1] + 1;
            }
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, 0), g(n, 0);
        f[0] = nums[0] > 0 ? 1 : 0;
        g[0] = nums[0] < 0 ? 1 : 0;
        int ans = f[0];

        for (int i = 1; i < n; ++i) {
            if (nums[i] > 0) {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] > 0 ? g[i - 1] + 1 : 0;
            } else if (nums[i] < 0) {
                f[i] = g[i - 1] > 0 ? g[i - 1] + 1 : 0;
                g[i] = f[i - 1] + 1;
            }
            ans = max(ans, f[i]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func getMaxLen(nums []int) int {
    n := len(nums)
    f := make([]int, n)
    g := make([]int, n)
    if nums[0] > 0 {
        f[0] = 1
    }
    if nums[0] < 0 {
        g[0] = 1
    }
    ans := f[0]

    for i := 1; i < n; i++ {
        if nums[i] > 0 {
            f[i] = f[i-1] + 1
            if g[i-1] > 0 {
                g[i] = g[i-1] + 1
            } else {
                g[i] = 0
            }
        } else if nums[i] < 0 {
            if g[i-1] > 0 {
                f[i] = g[i-1] + 1
            } else {
                f[i] = 0
            }
            g[i] = f[i-1] + 1
        }
        ans = max(ans, f[i])
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function getMaxLen(nums: number[]): number {
    const n = nums.length;
    const f: number[] = Array(n).fill(0);
    const g: number[] = Array(n).fill(0);

    if (nums[0] > 0) {
        f[0] = 1;
    }
    if (nums[0] < 0) {
        g[0] = 1;
    }

    let ans = f[0];
    for (let i = 1; i < n; i++) {
        if (nums[i] > 0) {
            f[i] = f[i - 1] + 1;
            g[i] = g[i - 1] > 0 ? g[i - 1] + 1 : 0;
        } else if (nums[i] < 0) {
            f[i] = g[i - 1] > 0 ? g[i - 1] + 1 : 0;
            g[i] = f[i - 1] + 1;
        }

        ans = Math.max(ans, f[i]);
    }

    return ans;
}

Solution 2: Dynamic Programming (Space Optimization)

Thinking

Each state uses only the previous \(f\) and \(g\), so two scalars replace the arrays. Time stays linear and extra memory becomes constant.

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)\).

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(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 = int(nums[0] > 0)
        g = int(nums[0] < 0)
        ans = f
        for i in range(1, n):
            ff = gg = 0
            if nums[i] > 0:
                ff = f + 1
                gg = 0 if g == 0 else g + 1
            elif nums[i] < 0:
                ff = 0 if g == 0 else g + 1
                gg = f + 1
            f, g = ff, gg
            ans = max(ans, f)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int f = nums[0] > 0 ? 1 : 0;
        int g = nums[0] < 0 ? 1 : 0;
        int ans = f;

        for (int i = 1; i < n; i++) {
            int ff = 0, gg = 0;
            if (nums[i] > 0) {
                ff = f + 1;
                gg = g == 0 ? 0 : g + 1;
            } else if (nums[i] < 0) {
                ff = g == 0 ? 0 : g + 1;
                gg = f + 1;
            }
            f = ff;
            g = gg;
            ans = Math.max(ans, f);
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        int f = nums[0] > 0 ? 1 : 0;
        int g = nums[0] < 0 ? 1 : 0;
        int ans = f;

        for (int i = 1; i < n; i++) {
            int ff = 0, gg = 0;
            if (nums[i] > 0) {
                ff = f + 1;
                gg = g == 0 ? 0 : g + 1;
            } else if (nums[i] < 0) {
                ff = g == 0 ? 0 : g + 1;
                gg = f + 1;
            }
            f = ff;
            g = gg;
            ans = max(ans, f);
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func getMaxLen(nums []int) int {
    n := len(nums)
    var f, g int
    if nums[0] > 0 {
        f = 1
    } else if nums[0] < 0 {
        g = 1
    }
    ans := f
    for i := 1; i < n; i++ {
        ff, gg := 0, 0
        if nums[i] > 0 {
            ff = f + 1
            gg = 0
            if g > 0 {
                gg = g + 1
            }
        } else if nums[i] < 0 {
            ff = 0
            if g > 0 {
                ff = g + 1
            }
            gg = f + 1
        }
        f, g = ff, gg
        ans = max(ans, f)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function getMaxLen(nums: number[]): number {
    const n = nums.length;
    let [f, g] = [0, 0];
    if (nums[0] > 0) {
        f = 1;
    } else if (nums[0] < 0) {
        g = 1;
    }
    let ans = f;
    for (let i = 1; i < n; i++) {
        let [ff, gg] = [0, 0];
        if (nums[i] > 0) {
            ff = f + 1;
            gg = g > 0 ? g + 1 : 0;
        } else if (nums[i] < 0) {
            ff = g > 0 ? g + 1 : 0;
            gg = f + 1;
        }
        [f, g] = [ff, gg];
        ans = Math.max(ans, f);
    }
    return ans;
}

Comments