LeetCode随机题：No.1567乘积为正数的最长子数组的长度。这是一道数组题，难度中等。原题请点这里：1567.积为正数的最长子数组的长度题目描述给你一个整数数组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]输出：4LeetCode被发现使用Performance测试例子：对于一个长度为100000的数组，除了nums[3000]为-1，其余均为1。解题思路问题重点：不包含0的数组，乘积是否为正number与否取决于其中负数的个数。当负数个数为偶数时，数组的乘积为正数。乘积是否为正数与该数的绝对值无关，而与该数在数组中的符号有关。因此，所有正数都可以转换为1，所有负数都可以转换为-1。题目需要一个连续数字的数组，所以出现0的地方自然要隔开。而如果拆分出来的子数组只有一个-1，说明这个子数组的乘积是负数（其他数全为1或者没有其他数），需要从-1的位置。在遍历子数组寻找满足条件的子数组长度时，先按照数组长度排序（Python排序很方便），从最长的数组开始查找，这样遍历就可以结束为尽快。解题过程如下图所示：先写一些实现各个小功能点的方法1.format_nums数字转换方法，输入n为数字，将正数转为1，负数转为-1，0保持不变defformat_nums(n):ifn>0:return1ifn<0:return-1return02划分子数组，先除以0，再除以唯一的-1。第一个是调用的cut_by_single_negative方法，它负责检查数组中是否只有一个-1。如果是这样，数组将被拆分，返回值将被统一到一个列表列表中。#子数组中没有0，检查是否只有一个-1#如果有且只有一个-1，说明这个子数组的乘积一定是负数，需要重新划分#如果有多个负数，没办法defcut_by_single_negative(sub_ls):ret_ls=[]ifsub_ls.count(-1)==1:idx=sub_ls.index(-1)ret_ls.append(sub_ls[:idx])ret_ls.append(sub_ls[idx+1:])else:ret_ls.append(sub_ls)returnret_ls可以验证这个方法：>>>cut_by_single_negative([1,1,1,1,-1,1])[[1,1,1,1],[1]]然后就是外层的调用方法cut_by_zero，按照0划分数组。#自然地将输入数组按0划分为子数组#对于每个子数组，检查是否只有一个-1，如果有，则必须划分defcut_by_zero(nums):#没有0的数组，check-1if0notinnums:returncut_by_single_negative(nums)#没有技巧，遍历数组，暂存在tmp中ret_ls=[]tmp=[]foriinnums:ifi==0:#If遍历到0，然后检查Checkiflen(tmp)!=0:ret_ls+=cut_by_single_negative(tmp)tmp=[]else:tmp.append(i)#不要忘记tailiflen(tmp)!=0:ret_ls+=cut_by_single_negative(tmp)返回ret_ls以验证此方法：>>>cut_by_zero([1,1,1,1,-1,1,0,1])[[1,1,1,1],[1],[1]]该方法在实现遍历过程时，采用了记录下标的方法来代替临时列表变量tmp，减少额外的内存开销。但是根据提交的结果来看，内存节省是有限的，而时间开销却增加了不少，推测与Python的list实现机制有关，所以这里保留使用临时变量的方法。3、is_positive方法，判断一个不包含0的子数组的乘积是否为正数，只需判断负数的个数是否为偶数即可。defis_positive(sub_nums):negative_count=sub_nums.count(-1)ifnegative_count%2==0:returnTrueelse:returnFalse也验证>>>print(is_positive([1,1,1,1]))>>>print(is_positive([-1,-1,1,-1]))TrueFalse4.getMaxLenofSub在不包含0的子数组中寻找满足条件的最长子数组，输入参数sub_nums为切分后的子数组数组，里面没有0，-1的个数不是1。先判断一些特殊情况，早点返回。defgetMaxLenofSub(sub_nums):len_sub=len(sub_nums)#如果子数组本身的乘积为正，则返回数组的长度ifis_positive(sub_nums):returnlen_sub#处理特殊情况，当子数组的长度为-array只有1，必须只有一个1iflen(sub_nums)==1:return1#满足条件的子数组，最长的就是子数组的长度#从最大长度向下递减，只要找到满足条件的子数组，就是最长子数组forlinrange(len_sub-1,0,-1):forindexinrange(len_sub-l+1):ifis_positive(sub_nums[index:index+l]):returnlreturn1验证:>>>print(getMaxLenofSub([1,1,1,1]))>>>print(getMaxLenofSub([-1,-1,1,-1]))435.最后整体的过程，先做数字转换，然后再分成子数组，再根据子数组的长度排序，这样遍历过程可以以后尽快结束。最后遍历所有子数组，找到满足条件的数组长度。defgetMaxLen(nums):#先将正负整数替换为1和-1nums=[format_nums(x)forxinnums]#按0划分子数组ls=cut_by_zero(nums)#按长度子数组排序ls.sort(key=lambdax:len(x),reverse=True)#记录当前满足条件的最长子数组长度，初值为0max_len_of_all=0#遍历所有子数组arraysforsub_numsinls:#如果遍历到的子数组长度小于max_len_of_all#说明不可能得到更长的合格子数组#而且数组是按长度排序的，所以可以得出结论max_len_of_all为最大值iflen(sub_nums)
