【算法挨揍日记】day27——152. 乘积最大子数组、1567. 乘积为正数的最长子数组长度

落日映苍穹つ 2024-02-19 11:40 41阅读 0赞

## 152. 乘积最大子数组 ##

[152. 乘积最大子数组][152.]

### 题目描述： ###

给你一个整数数组 `nums` ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 **32-位** 整数。

**子数组** 是数组的连续子序列。

![847c3ff131e1425690fc2d2392e35fcf.png][]

### 解题思路： ###

这道题与「最⼤⼦数组和」⾮常相似，我们可以效仿着定义⼀下状态表⽰以及状态转移：

i.  dp\[i\]  表⽰以  i  为结尾的所有⼦数组的最⼤乘积，

ii.  dp\[i\] = max(nums\[i\], dp\[i - 1\] \* nums\[i\])  ；

由于正负号的存在，我们很容易就可以得到，这样求  dp\[i\]  的值是不正确的。因为  dp\[i -

1\]  的信息并不能让我们得到  dp\[i\]  的正确值。⽐如数组  \[-2, 5, -2\]  ，⽤上述状态转移得

到的 dp数组为  \[-2, 5, -2\]  ，最⼤乘积为  5  。但是实际上的最⼤乘积应该是所有数相乘，结

果为  20  。

究其原因，就是因为我们在求  dp\[2\]  的时候，因为  nums\[2\]  是⼀个负数，因此我们需要的是

「  i - 1  位置结尾的最⼩的乘积 （ \-10 ） 」，这样⼀个负数乘以「最⼩值」，才会得到真实的

最⼤值。

因此，我们不仅需要⼀个「乘积最⼤值的  dp  表」，还需要⼀个「乘积最⼩值的  dp  表」。

1.  状态表⽰：

f\[i\]  表⽰：以  i  结尾的所有⼦数组的最⼤乘积，

g\[i\]  表⽰：以  i  结尾的所有⼦数组的最⼩乘积。

2.  状态转移⽅程：

遍历每⼀个位置的时候，我们要同步更新两个  dp  数组的值。

对于  f\[i\]  ，也就是「以  i  为结尾的所有⼦数组的最⼤乘积」，对于所有⼦数组，可以分为下

⾯三种形式：

i.  ⼦数组的⻓度为  1  ，也就是  nums\[i\]  ；

ii.  ⼦数组的⻓度⼤于  1  ，但  nums\[i\] > 0  ，此时需要的是  i - 1  为结尾的所有⼦数组

的最⼤乘积  f\[i - 1\]  ，再乘上  nums\[i\]  ，也就是  nums\[i\] \* f\[i - 1\]  ；

iii.  ⼦数组的⻓度⼤于  1  ，但  nums\[i\] < 0  ，此时需要的是  i - 1  为结尾的所有⼦数组

的最⼩乘积  g\[i - 1\]  ，再乘上  nums\[i\]  ，也就是  nums\[i\] \* g\[i - 1\]  ；

（如果  nums\[i\] = 0  ，所有⼦数组的乘积均为  0  ，三种情况其实都包含了）

综上所述，  f\[i\] = max(nums\[i\], max(nums\[i\] \* f\[i - 1\], nums\[i\] \* g\[i -

1\]) )。

对于  g\[i\]  ，也就是「以  i  为结尾的所有⼦数组的最⼩乘积」，对于所有⼦数组，可以分为下

⾯三种形式：

i.  ⼦数组的⻓度为  1  ，也就是  nums\[i\]  ；

ii.  ⼦数组的⻓度⼤于  1  ，但  nums\[i\] > 0  ，此时需要的是  i - 1  为结尾的所有⼦数组

的最⼩乘积  g\[i - 1\]  ，再乘上  nums\[i\]  ，也就是  nums\[i\] \* g\[i - 1\]  ；

iii.  ⼦数组的⻓度⼤于  1  ，但  nums\[i\] < 0  ，此时需要的是  i - 1  为结尾的所有⼦数组

的最⼤乘积  f\[i - 1\]  ，再乘上  nums\[i\]  ，也就是  nums\[i\] \* f\[i - 1\]  ；

综上所述，  g\[i\] = min(nums\[i\], min(nums\[i\] \* f\[i - 1\], nums\[i\] \* g\[i -

1\]))  。

（如果  nums\[i\] = 0  ，所有⼦数组的乘积均为  0  ，三种情况其实都包含了）

3.  初始化：

可以在最前⾯加上⼀个辅助结点，帮助我们初始化。使⽤这种技巧要注意两个点：

i.  辅助结点⾥⾯的值要保证后续填表是正确的；

ii.  下标的映射关系。

在本题中，最前⾯加上⼀个格⼦，并且让  f\[0\] = g\[0\] = 1  即可。

4.  填表顺序：

根据状态转移⽅程易得，填表顺序为「从左往右，两个表⼀起填」。

5.  返回值：

返回  f  表中的最⼤值。

### 解题代码： ###

class Solution {
    public:
        int maxProduct(vector<int>& nums) {
            int n=nums.size();
            if(n==1)return nums[0];
            vector<int>f(n,0);
            vector<int>g(n,0);
            f[0]=nums[0];g[0]=nums[0];
            for(int i=1;i<n;i++)
            {
                f[i]=max(max(f[i-1]*nums[i],g[i-1]*nums[i]),nums[i]);
                g[i]=min(min(g[i-1]*nums[i],nums[i]*f[i-1]),nums[i]);
            }
            int ret=INT_MIN;
            for(int i=0;i<n;i++)ret=max(ret,f[i]);
            return ret;
            
        }
    };

## 1567. 乘积为正数的最长子数组长度 ##

[1567. 乘积为正数的最长子数组长度][1567.]

### 题目描述： ###

给你一个整数数组 `nums` ，请你求出乘积为正数的最长子数组的长度。

一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。

请你返回乘积为正数的最长子数组长度。![30ded4a11a0c4816a04b703cd1fca939.png][]

### 解题思路： ###

算法思路：

继续效仿「最⼤⼦数组和」中的状态表⽰，尝试解决这个问题。

状态表⽰：  dp\[i\]  表⽰「所有以 i 结尾的⼦数组，乘积为正数的最⻓⼦数组的⻓度」。

思考状态转移：对于  i  位置上的  nums\[i\]  ，我们可以分三种情况讨论：

i.  如果  nums\[i\] = 0  ，那么所有以  i  为结尾的⼦数组的乘积都不可能是正数，此时

dp\[i\] = 0  ；

ii.  如果  nums\[i\] > 0  ，那么直接找到  dp\[i - 1\]  的值（这⾥请再读⼀遍  dp\[i -

1\]  代表的意义，并且考虑如果  dp\[i - 1\]  的结值是 0 的话，影不影响结果），然后加

⼀即可，此时  dp\[i\] = dp\[i - 1\] + 1  ；

iii.  如果  nums\[i\] < 0  ，这时候你该蛋疼了，因为在现有的条件下，你根本没办法得到此时

的最⻓⻓度。因为乘法是存在「负负得正」的，单单靠⼀个  dp\[i - 1\]  ，我们⽆法推导

出  dp\[i\]  的值。

但是，如果我们知道「以  i - 1  为结尾的所有⼦数组，乘积为负数的最⻓⼦数组的⻓

度」  neg\[i - 1\]  ，那么此时的  dp\[i\]  是不是就等于  neg\[i - 1\] + 1  呢？

通过上⾯的分析，我们可以得出，需要两个  dp  表，才能推导出最终的结果。不仅需要⼀个「乘积

为正数的最⻓⼦数组」，还需要⼀个「乘积为负数的最⻓⼦数组」。

1.  状态表⽰：

f\[i\]  表⽰：以  i  结尾的所有⼦数组中，乘积为「正数」的最⻓⼦数组的⻓度；

g\[i\]  表⽰：以  i  结尾的所有⼦数组中，乘积为「负数」的最⻓⼦数组的⻓度。

2.  状态转移⽅程：

遍历每⼀个位置的时候，我们要同步更新两个  dp  数组的值。

对于  f\[i\]  ，也就是以  i  为结尾的乘积为「正数」的最⻓⼦数组，根据  nums\[i\]  的值，可以

分为三种情况：

i.  nums\[i\] = 0  时，所有以  i  为结尾的⼦数组的乘积都不可能是正数，此时  f\[i\] =

0  ；

ii.  nums\[i\] > 0  时，那么直接找到  f\[i - 1\]  的值（这⾥请再读⼀遍  f\[i - 1\]  代表

的意义，并且考虑如果  f\[i - 1\]  的结值是  0  的话，影不影响结果），然后加⼀即可，

此时  f\[i\] = f\[i - 1\] + 1  ；

iii.  nums\[i\] < 0  时，此时我们要看  g\[i - 1\]  的值（这⾥请再读⼀遍  g\[i - 1\]  代

表的意义。因为负负得正，如果我们知道以  i - 1  为结尾的乘积为负数的最⻓⼦数组的

⻓度，加上  1  即可），根据  g\[i - 1\]  的值，⼜要分两种情况：

1.  g\[i - 1\] = 0  ，说明以  i - 1  为结尾的乘积为负数的最⻓⼦数组是不存在的，⼜

因为  nums\[i\] < 0  ，所以以  i  结尾的乘积为正数的最⻓⼦数组也是不存在的，此

时  f\[i\] = 0  ；

2.  g\[i - 1\] != 0  ，说明以  i - 1  为结尾的乘积为负数的最⻓⼦数组是存在的，⼜

因为  nums\[i\] < 0  ，所以以  i  结尾的乘积为正数的最⻓⼦数组就等于  g\[i -

1\] + 1  ；

综上所述，  nums\[i\] < 0  时，  f\[i\] = g\[i - 1\] == 0 ? 0 : g\[i - 1\] +

对于  g\[i\]  ，也就是以  i  为结尾的乘积为「负数」的最⻓⼦数组，根据  nums\[i\]  的值，可以

分为三种情况：

i.  nums\[i\] = 0  时，所有以  i  为结尾的⼦数组的乘积都不可能是负数，此时  g\[i\] =

0  ；

ii.  nums\[i\] < 0  时，那么直接找到  f\[i - 1\]  的值（这⾥请再读⼀遍  f\[i - 1\]  代表

的意义，并且考虑如果  f\[i - 1\]  的结值是  0  的话，影不影响结果），然后加⼀即可

（因为正数 \* 负数 = 负数），此时  g\[i\] = f\[i - 1\] + 1  ；

iii.  nums\[i\] > 0  时，此时我们要看  g\[i - 1\]  的值（这⾥请再读⼀遍  g\[i - 1\]  代

表的意义。因为正数 \* 负数 = 负数），根据  g\[i - 1\]  的值，⼜要分两种情况：

1.  g\[i - 1\] = 0  ，说明以  i - 1  为结尾的乘积为负数的最⻓⼦数组是不存在的，⼜

因为  nums\[i\] > 0  ，所以以  i  结尾的乘积为负数的最⻓⼦数组也是不存在的，此

时  f\[i\] = 0  ；

2.  g\[i - 1\] != 0  ，说明以  i - 1  为结尾的乘积为负数的最⻓⼦数组是存在的，⼜

因为  nums\[i\] > 0  ，所以以  i  结尾的乘积为正数的最⻓⼦数组就等于  g\[i -

1\] + 1  ；

综上所述，  nums\[i\] > 0  时，  g\[i\] = g\[i - 1\] == 0 ? 0 : g\[i - 1\] +

1  ;

这⾥的推导⽐较绕，因为不断的出现「正数和负数」的分情况讨论，我们只需根据下⾯的规则，严

格找到此状态下需要的  dp  数组即可：

i.  正数 \* 正数 = 正数

ii.  负数 \* 负数 = 正数

iii.  负数 \* 正数 = 正数 \* 负数 = 负数

3.  初始化：

可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点：

i.  辅助结点⾥⾯的值要「保证后续填表是正确的」；

ii.  「下标的映射关系」。

在本题中，最前⾯加上⼀个格⼦，并且让  f\[0\] = g\[0\] = 0  即可。

4.  填表顺序：

根据「状态转移⽅程」易得，填表顺序为「从左往右，两个表⼀起填」。

5.  返回值：

根据「状态表⽰」，我们要返回  f  表中的最⼤值。

### 解题代码： ###

class Solution {
    public:
        int getMaxLen(vector<int>& nums) {
            int n=nums.size();
            vector<int>f(n+1,0);
            vector<int>g(n+1,0);
            int ret=INT_MIN;
            for(int i=1;i<=n;i++)
            {
                if(nums[i-1]>0)
                {
                    f[i]=f[i-1]+1;
                    g[i]=g[i-1]==0?0:g[i-1]+1;
                }
                else if(nums[i-1]<0)
                {
                    g[i]=f[i-1]+1;
                    f[i]=g[i-1]==0?0:g[i-1]+1;
                }
                ret=max(ret,f[i]);
            }
            return ret;
        }
    };

[152.]: https://leetcode.cn/problems/maximum-product-subarray/
[847c3ff131e1425690fc2d2392e35fcf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/a5145a37f542448a8b3b2bc5588ecb18.png
[1567.]: https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/
[30ded4a11a0c4816a04b703cd1fca939.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/b2f6fc96b27a49bab41f55cf0bd35869.png