题目描述
给你一个整数数组 nums ,请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
C++ 代码
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
//用二维的dp数组表示状态
//dp[i][j] 表示以j位置元素结尾的乘积情况为i的最长子数组长度(i == 0 表示负 i == 1 表示正)
vector<vector<int>> dp(2, vector<int>(n));
if(nums[0] > 0){
dp[0][0] = 0, dp[1][0] = 1;
}
else if(nums[0] == 0){
dp[0][0] = dp[1][0] = 0;
}
else{
dp[0][0] = 1, dp[1][0] = 0;
}
for(int i = 1; i < n; ++i){
if(nums[i] > 0){
//如果是正数的话,子数组乘积为 负 只能从上一段子数组乘积为 负 的情况转移
dp[0][i] = dp[0][i - 1] ? dp[0][i - 1] + 1 : 0;
//子数组乘积为 正 只能从上一段子数组乘积为 正 的情况转移
dp[1][i] = dp[1][i - 1] + 1;
}
else if(nums[i] == 0){
dp[0][i] = dp[1][i] = 0;
}
else if(nums[i] < 0){
//如果是负数的话,子数组乘积为 正 只能从上一段子数组乘积为 负 的情况转移
dp[1][i] = dp[0][i - 1] ? dp[0][i - 1] + 1 : 0;
//子数组乘积为 负 只能从上一段子数组乘积为 正 的情况转移
dp[0][i] = dp[1][i - 1] + 1;
}
}
//最后返回正数dp数组的最大值
return *max_element(dp[1].begin(), dp[1].end());
}
};