LeetCode 1567. Maximum Length of Subarray With Positive Product Solution in Java, C++, Python & More | Explanation + Code

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

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

Initially, if nums[0] > 0, then f[0] = 1, otherwise f[0] = 0; if nums[0] < 0, then g[0] = 1, otherwise g[0] = 0. We initialize the answer ans = f[0].

Next, we iterate through the array nums starting from i = 1. For each i, we have the following cases:

• If 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 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 nums.

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

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

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)