暂无图片
暂无图片
暂无图片
暂无图片
暂无图片

golang刷leetcode 技巧(76) 乘积为正数的最长子数组长度

给你一个整数数组 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] 。

示例 4:


输入:nums = [-1,2]

输出:1

示例 5:


输入:nums = [1,2,3,5,-6,4,0,10]

输出:4

 


提示:


1 <= nums.length <= 10^5

-10^9 <= nums[i] <= 10^9


解题思路

1,本题可以拆解成子问题

2,子问题1:如果含有0,从0的位置截断,取左右两部分的大值

3,子问题2:如果不含0,统计所有负数下标

4,对子问题2,又可以拆分成两个子问题

5,子问题2.1:负数有 偶数个,直接返回长度

6,子问题2.2:负数有奇数个,应该从第一个负数,或者最后一个负数的位置截断

7,计算截断后的最大长度

8,子问题一般递归比较好解决。


代码实现

    func getMaxLen(nums []int) int {
    var negIndex []int
    for i:=0;i<len(nums);i++{
    if nums[i]==0{
    l:=getMaxLen(nums[:i:i])
    r:=0
    if i<len(nums)-1{
    r=getMaxLen(nums[i+1:])
    }
    if l>r{
    return l
    }
    return r
    }
    if nums[i]<0{
    negIndex=append(negIndex,i)
    }
    }
    if len(negIndex)%2==0{
    return len(nums)
    }
    ri:=negIndex[len(negIndex)-1]
    rl:=[]int{negIndex[0],len(nums)-negIndex[0]-1,len(nums)-ri-1,ri}
    max:=0
    for _,v:=range rl{
    if v>max{
    max=v
    }
    }
    return max
    }


    文章转载自golang算法架构leetcode技术php,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

    评论