写在前面

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

题目

思路分析

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

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

图解

情况一：nums[i] == 0

由于 nums[i] == 0，无论之前是正数乘积还是负数乘积均变为0，所以对应的长度也均变为0，即：f[i + 1] = g[i + 1] = 0;

情况二：nums[i] > 0

对于 nums[i] > 0 的情况，f 本身就表示大于零的乘积长度，故直接将旧的 f 值加一即可：f[i + 1] = f[i] + 1; 而对于 g ，如果原来存在乘积为负数，再乘上一个正数不改变符号，增加长度：g[i + 1] = g[i] + 1; 不过如果原来不存在乘积为负数，那么乘一个正数也得不到负数的结果，所以应该为0，即：g[i + 1] = g[i] > 0 ? g[i] + 1: 0;

情况三：nums[i] < 0

在这一步中，遇到负数，由于 f 原来的长度为1，乘上负数变为负数，所以 g[i + 1] = f[i] + 1; 而原来不存在乘积为负数(g[i] == 0)，所以乘上一个负数后不存在乘积为正数，即：f[i + 1] = 0; 然后再来考虑下边的情况

由于原来存在乘积为负数的长度g[i]，再乘上一个负数变为正数，所以有 f[i + 1] = g[i] + 1; 原来不存在乘积为正数的长度，但是当前位置元素为负数，所以 g[i + 1] = 1; 也可以写成 g[i + 1] = f[i] + 1;
综合这两种情况考虑，可以得到如下的递推公式：

    //原乘积为负的子数组变正，乘积为正的子数组变负
    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、贪心的影子，想要直接写出最终优化空间后的代码还是挺难的，不过想通可能的状况，用数组记录状态来求解还是很容易想到的。
如果有什么写的不对的地方还请指出，感恩相遇~