【动态规划刷题 10】最大子数组和 III && 环形子数组的最大和

简介: 【动态规划刷题 10】最大子数组和 III && 环形子数组的最大和

152. 乘积最大子数组

链接: 152. 乘积最大子数组

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


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


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


示例 1:


输入: nums = [2,3,-2,4]

输出: 6

解释: 子数组 [2,3] 有最大乘积 6。

示例 2:


输入: nums = [-2,0,-1]

输出: 0

解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。


1.状态表示*

定义两个状态表示:


f[i] 表⽰:以 i 结尾的所有⼦数组的最⼤乘积。

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


2.状态转移方程


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

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

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

对于g[i],也就是「以 i 为结尾的所有⼦数组的最小乘积」,可以分为:

  1. 当nums[i]>0 时, g[i]=g[i-1]*nums[i];
  2. 当nums[i]<0时,g[i]=min(f[i-1]*nums[i],nums[i]);

3. 初始化

对于这些初始化较为简单的题,没有添加辅助节点,直接进行初始化

        f[0]=nums[0]>0?nums[0]:0;
        g[0]=nums[0]>0?0:nums[0];

4. 填表顺序

根据「状态转移⽅程」易得,填表顺序为「从左往右」,其两个表一起填写

5. 返回值

返回f[]表中的最大值

代码:

 int maxProduct(vector<int>& nums) {
        int n=nums.size();
        //f表示乘积最大子数组的乘积
        //g表示乘积最小子数组的乘积
        vector<int> f(n),g(n);
        int Max=nums[0];
        f[0]=nums[0]>0?nums[0]:0;
        g[0]=nums[0]>0?0:nums[0];
        for(int i=1;i<n;i++)
        {
            if(nums[i]>0)
            {
                f[i]=max(f[i-1]*nums[i],nums[i]);
                g[i]=g[i-1]*nums[i];
            }
            if(nums[i]<0)
            {
                f[i]=g[i-1]*nums[i];
                g[i]=min(f[i-1]*nums[i],nums[i]);
            }
           // cout<<f[i]<<" "<<g[i]<<endl;
            Max=max(Max,f[i]);
        }
        return Max;                                                   
    }

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

链接: 1567. 乘积为正数的最长子数组长度

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


1.状态表示*

定义两个状态表示:


f[i] 表⽰:以 i 结尾的所有⼦数组的乘积为正数的最长子数组长度。

g[i] 表⽰:以 i 结尾的所有⼦数组的乘积为负数的最长子数组长度。


2.状态转移方程


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

对于 f[i] ,也就是「以 i 结尾的所有⼦数组的乘积为正数的最长子数组长度」,对于所有⼦数组,可以分为:

  1. 当nums[i]>0 时, f[i]=f[i-1]+1;
  2. 当nums[i]<0时,f[i]=g[i-1]==0?0:g[i-1]+1;

对于g[i],也就是「以 i 为结尾的所有⼦数组的最小乘积」,可以分为:

  1. 当nums[i]>0 时, g[i]=g[i-1]==0?0:g[i-1]+1;
  2. 当nums[i]<0时,g[i]=f[i-1]+1;

3. 初始化

对于这些初始化较为简单的题,没有添加辅助节点,直接进行初始化

         if(nums[0]>0) f[0]=1;
        else if(nums[0]<0) g[0]=1;

4. 填表顺序

根据「状态转移⽅程」易得,填表顺序为「从左往右」,其两个表一起填写

5. 返回值

返回f[]表中的最大值

代码:

 int getMaxLen(vector<int>& nums) {
        int n=nums.size();
        //以 i位置为最后一个位置时
        //f[] 表示的正,g[]表示的是负
        vector<int> f(n),g(n);
        if(n==1)
        {
            if(nums[0]>0) return 1;
            else return 0;
        }
        if(nums[0]>0) f[0]=1;
        else if(nums[0]<0) g[0]=1;
        int Max=0;
        for(int i=1;i<n;i++)
        {
            if(nums[i]>0)
            {
                f[i]=f[i-1]+1;
                g[i]=g[i-1]==0?0:g[i-1]+1;
            }
            if(nums[i]<0)
            {
                f[i]=g[i-1]==0?0:g[i-1]+1;
                g[i]=f[i-1]+1;
            }
            if(nums[i]==0)
            {
                f[i]=g[i]=0;
            }
            Max=max(Max,f[i]);
        }
        return Max;
    }
相关文章
|
算法
【学会动态规划】环形子数组的最大和(20)
【学会动态规划】环形子数组的最大和(20)
59 0
|
算法
【学会动态规划】最大子数组和(19)
【学会动态规划】最大子数组和(19)
46 0
|
机器学习/深度学习 算法
【动态规划刷题 9】最大子数组和 III && 环形子数组的最大和
【动态规划刷题 9】最大子数组和 III && 环形子数组的最大和
|
6月前
|
算法 测试技术
【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和1
【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和1
53 1
|
6月前
|
机器学习/深度学习 算法
【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和
【动态规划专栏】专题四:子数组问题--------最大子数组和&&环形子数组的最大和
56 1
|
5月前
|
Java
蓝桥杯-动态规划专题-子数组系列,双指针
蓝桥杯-动态规划专题-子数组系列,双指针
|
5月前
蓝桥杯-动态规划-子数组问题
蓝桥杯-动态规划-子数组问题
|
算法
【算法专题突破】双指针 - 四数之和(8)
【算法专题突破】双指针 - 四数之和(8)
31 0
|
C++
剑指offer 53. 数组中的逆序对
剑指offer 53. 数组中的逆序对
77 0
剑指offer 53. 数组中的逆序对
|
人工智能 算法
【数据结构与算法】数组2:双指针法 & 二分法(螺旋矩阵)
【数据结构与算法】数组2:双指针法 & 二分法(螺旋矩阵)
96 0