1567. Maximum Length of Subarray With Positive Product
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].
Example 4:
Input: nums = [-1,2] Output: 1
Example 5:
Input: nums = [1,2,3,5,-6,4,0,10] Output: 4
Constraints:
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
给一个数组，包含正数、负数和0，问最长连乘结果为正的长度是多少。
本题与LeetCode Maximum Product Subarray类似，要注意负负得正的情况。首先是传统DP好理解方法：设置dp_pos和dp_neg两个数组，分别表示遍历到i时，当前的最长连乘为正的长度和最长连乘为负的长度。则对于第i个位置，如果nums[i]是正数，则dp_pos直接+1；对于dp_neg，如果前一刻已经是连乘为负，即dp_neg[i-1]>0，则在前一刻基础上再乘以nums[i]还是负，所以负数长度可变长，即dp_neg+1；如果前一刻没有连乘为负，则增加一个正数也不会使连乘为负的长度增加，所以dp_neg=0。类似的可以讨论num[i]为负数的情况。如果nums[i]==0，则dp_pos和dp_neg都重置为0。
完整代码如下：
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
vector<int> dp_pos(n, 0), dp_neg(n, 0);
if(nums[0] > 0) dp_pos[0] = 1;
else if(nums[0] < 0) dp_neg[0] = 1;
int ans = dp_pos[0];
for(int i = 1; i < n; ++i) {
if(nums[i] > 0) {
dp_pos[i] = dp_pos[i - 1] + 1;
dp_neg[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
} else if(nums[i] < 0) {
dp_pos[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
dp_neg[i] = dp_pos[i - 1] + 1;
}
ans = max(ans, dp_pos[i]);
}
return ans;
}
};本代码提交AC，用时268MS。
因为DP只用到上一刻的状态，所以不用数组存储也可以，节省内存版本如下，不过需要注意tmp=pos_len保存上一刻的pos_len状态。
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
int pos_len = 0, neg_len = 0;
if(nums[0] > 0) pos_len = 1;
else if(nums[0] < 0) neg_len = 1;
int ans = pos_len;
for(int i = 1; i < n; ++i) {
if(nums[i] > 0) {
++pos_len;
neg_len = neg_len > 0 ? neg_len + 1 : 0;
} else if(nums[i] < 0) {
int tmp = pos_len;
pos_len = neg_len > 0 ? neg_len + 1 : 0;
neg_len = tmp + 1;
} else if(nums[i] == 0) {
pos_len = neg_len = 0;
}
ans = max(ans, pos_len);
}
return ans;
}
};本代码提交AC，用时368MS。