Welcome to Subscribe On Youtube
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
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}$.
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 $\textit{nums}$. The space complexity is $O(1)$.
-
class Solution { public int getMaxLen(int[] nums) { int f1 = nums[0] > 0 ? 1 : 0; int f2 = nums[0] < 0 ? 1 : 0; int res = f1; for (int i = 1; i < nums.length; ++i) { if (nums[i] > 0) { ++f1; f2 = f2 > 0 ? f2 + 1 : 0; } else if (nums[i] < 0) { int pf1 = f1, pf2 = f2; f2 = pf1 + 1; f1 = pf2 > 0 ? pf2 + 1 : 0; } else { f1 = 0; f2 = 0; } res = Math.max(res, f1); } return res; } } // Solution 2 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; } } -
class Solution { public: int getMaxLen(vector<int>& nums) { int f1 = nums[0] > 0 ? 1 : 0; int f2 = nums[0] < 0 ? 1 : 0; int res = f1; for (int i = 1; i < nums.size(); ++i) { if (nums[i] > 0) { ++f1; f2 = f2 > 0 ? f2 + 1 : 0; } else if (nums[i] < 0) { int pf1 = f1, pf2 = f2; f2 = pf1 + 1; f1 = pf2 > 0 ? pf2 + 1 : 0; } else { f1 = 0; f2 = 0; } res = max(res, f1); } return res; } }; // Solution 2 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; } }; -
class Solution: def getMaxLen(self, nums: List[int]) -> int: f1 = 1 if nums[0] > 0 else 0 f2 = 1 if nums[0] < 0 else 0 res = f1 for num in nums[1:]: pf1, pf2 = f1, f2 if num > 0: f1 += 1 if f2 > 0: f2 += 1 else: f2 = 0 elif num < 0: pf1, pf2 = f1, f2 f2 = pf1 + 1 if pf2 > 0: f1 = pf2 + 1 else: f1 = 0 else: f1 = 0 f2 = 0 res = max(res, f1) return res # Solution 2 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 -
func getMaxLen(nums []int) int { f1, f2 := 0, 0 if nums[0] > 0 { f1 = 1 } if nums[0] < 0 { f2 = 1 } res := f1 for i := 1; i < len(nums); i++ { if nums[i] > 0 { f1++ if f2 > 0 { f2++ } else { f2 = 0 } } else if nums[i] < 0 { pf1, pf2 := f1, f2 f2 = pf1 + 1 if pf2 > 0 { f1 = pf2 + 1 } else { f1 = 0 } } else { f1, f2 = 0, 0 } res = max(res, f1) } return res } // Solution 2 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 } -
function getMaxLen(nums: number[]): number { // 连续正数计数n1, 连续负数计数n2 let n1 = nums[0] > 0 ? 1 : 0, n2 = nums[0] < 0 ? 1 : 0; let ans = n1; for (let i = 1; i < nums.length; ++i) { let cur = nums[i]; if (cur == 0) { (n1 = 0), (n2 = 0); } else if (cur > 0) { ++n1; n2 = n2 > 0 ? n2 + 1 : 0; } else { let t1 = n1, t2 = n2; n1 = t2 > 0 ? t2 + 1 : 0; n2 = t1 + 1; } ans = Math.max(ans, n1); } return ans; } // Solution 2 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; }