一起学习交流~

乘积为正数的最长子数组长度-dp两种情况

算法 laomuji 8个月前 (02-02) 354次浏览 已收录 0个评论

目录

题目

给你一个整数数组 nums ,请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例  1:
输入:nums = [1,-2,-3,4]
输出:4
解释:数组本身乘积就是正数,值为 24 。
示例 2:
输入:nums = [0,1,-2,-3,-4]
输出:3
解释:最长乘积为正数的子数组为 [1,-2,-3] ,乘积为 6 。
注意,我们不能把 0 也包括到子数组中,因为这样乘积为 0 ,不是正数。
示例 3:
输入:nums = [-1,-2,-3,0,1]
输出:2
解释:乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-length-of-subarray-with-positive-product
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

class Solution {
/*
求乘积为正数的最长子数组长度
定义两个变量
一个记录正数长度
一个记录负数长度
f(x)以当前数字结尾时
当前数字为正数时 不会改变 正负性质
当前数字为负数时 会改变   正负性质
当前数字为零时   会重置   正负计数
1,-2,-3,4,-5

1
positive = 1
negative = 0

1 -2
positive = 0
negative = 2

1 -2 -3
positive = 3
negative = 1

1,-2,-3,4
positive = 4
negative = 2

1,-2,-3,4,-5
positive = 0
negative = 5

*/
public:
    int getMaxLen(vector<int>& nums) {
        int size = nums.size();
        int positive = nums[0]>0?1:0;
        int negative = nums[0]<0?1:0;
        int maxLen = positive;
        int positiveTemp;
        int negativeTemp;
        for(int i = 1;i<size;i++){
            if(nums[i]>0){
                //正数直接+1
                positiveTemp=positive = positive+1;
                //负数个数不为零 乘正数 才能为负数
                negativeTemp=negative = negative>0?negative+1:0;
            }else if(nums[i]<0){
                //正数乘负数 会变为负数
                //相反的 负数*负数会变为正数
                //只有当有负数时,才能乘负数变为正数
                positiveTemp = negative>0?negative+1:0;
                //正数*负数为负数
                //无论是否有正数,都会变为负数
                //所以直接+1即可
                negativeTemp = positive+1;
            }else{
                positiveTemp = 0;
                negativeTemp = 0;
            }
            positive = positiveTemp;
            negative = negativeTemp;
            if(positive>maxLen)maxLen=positive;
        }

        return maxLen;
    }
};
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论