LeetCode刷题笔记-动态规划-day6

我会带着你远行 2023-10-01 18:12 50阅读 0赞

#### 文章目录 ####

*  LeetCode刷题笔记-动态规划-day6
 *   *  152. 乘积最大子数组
     *   *  1.题目
         *  2.解题思路
         *  3.代码
     *  1567. 乘积为正数的最长子数组长度
     *   *  1.题目
         *  2.解题思路
         *  3.代码

## LeetCode刷题笔记-动态规划-day6 ##

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

#### 1.题目 ####

> 原题链接：[152. 乘积最大子数组][152.]

![image-20220212101240798][]

#### 2.解题思路 ####

算法：动态规划 + 滚动数组优化

1.  f\[i\]表示所有从0到i并且选用a\[i\]获得的最大乘积
2.  g\[i\]表示所有从0到i并且选用a\[i\]获得的最小乘积

则有这样几种情况：

*  当a\[i\] >= 0时，f\[i\] = max(a\[i\], f\[i - 1\] \* a\[i\])
 *  当a\[i\] < 0时，f\[i\] = max(a\[i\], g\[i - 1\] \* a\[i\])
 *  当a\[i\] >= 0时，g\[i\] = min(a\[i\], g\[i - 1\] \* a\[i\])
 *  当a\[i\] < 0时，g\[i\] = min(a\[i\], f\[i - 1\] \* a\[i\])

可以合并为：

1.  当`a[i] >= 0`时 `f[i] = max(a[i], max(f[i-1] * a[i],g[i-1]*a[i]))`
2.  当`a[i]<0`时`f[i] = max(a[i], max(g[i-1] * a[i],f[i-1]*a[i])`

可以用滚动数组优化空间。详细见代码。

#### 3.代码 ####

class Solution {
        
    public:
        int maxProduct(vector<int>& a) {
        
            int f=a[0],g=a[0];
            int res=a[0];
            for(int i=1;i<a.size();i++){
        
                int t=a[i],fa=f*t,ga=g*t;
                f=max(t,max(fa,ga));
                g=min(t,min(fa,ga));
                res=max(res,f);
            }
            return res;
        }
    };

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

#### 1.题目 ####

> 原题链接：[1567. 乘积为正数的最长子数组长度][1567.]

![image-20220212101316030][]

#### 2.解题思路 ####

算法：动态规划

我们可以用两个数组`f[i]`和`g[i]`：

*  `f[i]`表示以下标i结尾乘积为正数的最长子数组长度
 *  `g[i]`表示以下标i结尾乘积为负数的最长子数组长度

这里我们可以得到递推公式：

1.  如果当前数大于0，即`nums[i]>0`，之前的乘积乘以当前数，正负性是不会发生改变的，所以：
    
    1.  `f[i]=f[i-1]+1`
    2.  如果`g[i-1]`不等于0的话，才加一，如果g\[i-1\]本身为0，这里为正数也不会改变
2.  如果当前数小于0，即`nums[i]<0`，之前的乘积乘以当前数会改变乘积的正负性，所以：
    
    1.  这时候`g[i]`应该等于`f[i-1]+1`，因为`f[i-1]`包含的数乘积是正数，乘以当前数刚好为负数。
    2.  `f[i]`需要考虑`g[i-1]`情况，如果`g[i-1]`为0，这里`f[i]`也还是为0，否则`f[i]=g[i-1]+1`，负数乘负数为正数
3.  如果当前数为0，即`nums[i]==0`，将`f[i]`，`g[i]`赋值为0
4.  每次遍历维护最大值：`res=max(res,f[i]);`

#### 3.代码 ####

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

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[152.]: https://leetcode-cn.com/problems/maximum-product-subarray/
[image-20220212101240798]: https://img-blog.csdnimg.cn/img_convert/904eb1cc036627171767aa545ddba513.png
[1567.]: https://leetcode-cn.com/problems/maximum-length-of-subarray-with-positive-product/
[image-20220212101316030]: https://img-blog.csdnimg.cn/img_convert/b86dfa8cacb9e31c2f44152ea4c7a673.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/6124fd5f09c24647832b9464ffd3ccdb.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16