写在前面

这道是上周周赛的第二题，我很惨，直接卡在这题，总共就AC了一道= =，真是菜爆了，跟着的闫老师讲解总算是搞懂了后边三道题，学到了一些新的东西，收获还是挺多的，所以将后三道题的解法记录下来。

题目

思路分析

其实看到这道题的时候我还感觉有点熟悉，之前做过一道乘积最大子数组，两者非常的像，都要考虑特殊的0与负数，所以一直向那道题的方向考虑，总想着一次遍历还不是用额外的空间，结果因为之前就没有理解的很透彻，导致自己陷到里边了，到最后也没做出来。
其实通过递推并使用数组保存中间计算的值就可以很轻松的计算出来了。
我们选用两个数组：

• f[i] 表示以 i 结尾的乘积为正数的子数组的最长长度
• g[i] 表示以 j 结尾的乘积为负数的子数组的最长长度
  使用两个数组的原因是：如果遇到原数组中的 nums[i] 为负数，则对应的正数乘积变负，而负数乘积变正，所以两个乘积长度均要保留下来方便计算。

图解

情况一：nums[i] == 0

情况二：nums[i] > 0

情况三：nums[i] < 0

    //原乘积为负的子数组变正，乘积为正的子数组变负
    f[i + 1] = g[i] > 0 ? g[i] + 1 : 0;
    g[i + 1] = f[i] + 1;

完整代码

综合以上三种情况，在每次遍历一个元素时保留最长的正数长度即可得到最终代码如下

public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1], g = new int[n + 1];
        int maxLen = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                f[i + 1] = f[i] + 1;
                g[i + 1] = g[i] > 0 ? g[i] + 1 : 0;
            }else if(nums[i] < 0){
                //原乘积为负的子数组变正，乘积为正的子数组变负
                f[i + 1] = g[i] > 0 ? g[i] + 1 : 0;
                g[i + 1] = f[i] + 1;
            }
            maxLen = Math.max(maxLen, f[i + 1]);
        }
        return maxLen;
    }

空间优化

可以发现每次要求解的值只与上一次计算的结果有关，所以可以用两个变量代替两个数组，从而节省空间。

public int getMaxLen(int[] nums) {
        int x = 0, y = 0;
        int maxLen = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 0){
                x = 0;
                y = 0;
            }else if(nums[i] > 0){
                x++;
                if(y > 0){
                    //截止到此有乘积为负数的子数组，多一个正数仍为负数
                    y++;
                }
                maxLen = Math.max(maxLen, x);
            }else{
                //交换，原乘积为负的子数组变正，乘积为正的子数组变负
                int temp = x;
                x = y;
                y = temp;

                //如果存在原乘积为负的子数组(x > 0)，那么乘积由负变正，否则不存在乘积为正的子数组，x = 0
                if(x > 0) x++;
                y++;
                maxLen = Math.max(maxLen, x);
            }
        }
        return maxLen;
    }

这种类型题有种DP、贪心的影子，想要直接写出最终优化空间后的代码还是挺难的，不过想通可能的状况，用数组记录状态来求解还是很容易想到的。
如果有什么写的不对的地方还请指出，感恩相遇~