【动态规划刷题 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];
1
2

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<
            Max=max(Max,f[i]);
        }
        return Max;                                                   
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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;
1
2

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35