LEETCODE 1567. Maximum Length of Subarray With Positive Product 解题思路分析

题目大意：

乘积为正数的最长子数组长度

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1567

解题思路分析：

这道题使用前缀乘积方式解题是非常合适的。

1. 首先我们先将问题简化，因为题目只关系正负，因此所有正数可以看做是1，负数是-1，0还是0。
2. 为了保证乘积为正数，子数组中一定不能包含0。即我们可以想象为，先将数组用元素0切割，然后再在每个子数组中找到乘积为正数的最长子数。（实际解题时并不用分割，这只是一个思路）
3. 从首位开始循环，计算前缀乘积。此时会有以下几种情况：
   1. 当前数字大于0，并且当前前缀乘积为正数时，那么当前前缀区间是一个合理区间，并用该区间长度更新全局最大长度。
   2. 当前数字大于0，并且当前前缀乘积为负数时，这是本题解法关键的一种模式，假设前缀区间起始下标为s，当前下标为i，当区间[s, i]的乘积为负数时，我们此时可以找到一个最小的前缀区间，并且该区间的前缀乘积也为负数（该区间可以在第一次遍历到负数前缀和时记录下来），比如[s, j]（j<i），因为[s, j] * [j+1, i] = [s, i]，同时已知[s, j]和[s, i]的乘积都是负数，那么[j+1, i]区间的乘积一定是正数，此时[j+1, i]是一个合理区间，并用该区间长度更新全局最大长度。
   3. 当前数字小于0，并且当前前缀乘积为正数时，那么当前前缀区间是一个合理区间，并用该区间长度更新全局最大长度。
   4. 当前数字小于0，并且当前前缀乘积为负数时，那么显然将当前前缀乘积除去当前的负数即是一个正数前缀区间，即[s, i-1]是一个合理区间，并用该区间长度更新全局最大长度。（这个区间实际上就是上面的情况C）
   5. 当前数字等于0（当前前缀乘积也必定是0）时，我们重新规划前缀区间，将前缀区间的首位置设置到当前位置加一。同时清空之前记录的首个前缀乘积负数区间。

实现代码：

public int getMaxLen(int[] nums) {
    int res=0; // 返回结果（最长区间）
    int firstIndex=0; // 前缀乘积区间首元素下标
    int firstMiunsIndex=-1; // 首个前缀乘积负数区间的下标
    int product=1; // 当前前缀乘积
    for(int i=0;i<nums.length;i++){ // 循环每个数字
        if(nums[i]>0){ // 当前数字大于0
            // 当前数字本身即是一个合理区间。使用长度1更新最大值
            res=Math.max(res,1);
            // 前缀乘积（因为只关心正负，所以不用实际乘每个数字，只乘1和-1即可）
            product*=1;
            // 前缀乘积为正数，当前前缀区间为合理区间
            if(product>0) res=Math.max(res,i-firstIndex+1);
            // 前缀乘积为负数，当前下标与首个负数前缀乘积区间之间的长度为一个合理区间
            else if(product<0) res= Math.max(res,i-firstMiunsIndex);
        }else if(nums[i]<0){ // 当前数字小于0
            product*=-1; // 前缀乘积
            // 前缀乘积为正数，当前前缀区间为合理区间
            if(product>0) res=Math.max(res,i-firstIndex+1);
            else if(product<0){ // 前缀乘积为负数，
                 // 如果首个负数前缀乘积区间尚未记录，记录下当前下标
                if(firstMiunsIndex==-1) firstMiunsIndex=i;
                 // 当前前缀乘积除去当前的负数即是一个正数前缀区间，即[s, i-1]是一个合理区间
                res=Math.max(res,i-firstIndex);
            }
        }else{ // 当前数字等于0
            product=1; // 重置前缀乘积
            firstIndex=i+1; // 前缀区间首元素为止为当前下标加一
            firstMiunsIndex=-1; // 清空首个负数前缀区间位置
        }
    }
    return res;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 80.00% of Java online submissions for Maximum Length of Subarray With Positive Product.

Memory Usage: 54.5 MB, less than 60.00% of Java online submissions for Maximum Length of Subarray With Positive Product.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1567-maximum-length-of-subarray-with-positive-product-解题思路分析/