动态规划（八）——子数组系列（求积问题）

这一篇博客我们继续来领略动态规划算法的魅力~准备好了吗~我们发车去探索动态规划的奥秘啦~🚗🚗🚗🚗🚗🚗

乘积最大子数组

乘积最大子数组

根据题目要求，这是希望我们求解得到一个子数组乘积最大的结果，同时这个数组里面还有负数，那么这个问题就不简单了~

按照我们常规的思路创建一个dp表表示以【i】位置为结尾的最大乘积，到【i】位置最大乘积有两种情况，一种是子数组长度为1，那么结果就是它本身；如果子数组长度大于1，那么就需要与前面的一个位置结合起来，如果nums【i】> 0,那么最大子数组乘积就等于nums【i】*dp【i-1】这没有问题，但是如果nums【i】< 0,再乘一个最大的乘积子数组，这不就把原来的也变小了嘛？所以nums【i】< 0的时候应该乘以前面一个位置的最小乘积子数组，这样才是以【i】位置为结尾的最大乘积~接下来我们结合动态规划思想进行分析~

分析：

1、状态表示

题目要求：求解数组最大的连续子数组乘积

结合这里的题目要求+经验+我们的分析，创建两个dp表，一个求最大子数组乘积，一个求最小子数组乘积： dp1表中的dp1[i]表示为以【i】位置为结尾最大子数组乘积~ dp2表中的dp2[i]表示为以【i】位置为结尾最小子数组乘积~

2、状态转移方程

我们以离【i】位置最近的状态分析状态转移方程，处理dp1表 既然状态表示为： 以【i】位置为结尾最大子数组乘积~ ，那么第i个位置肯定在子数组中，那么以【i】位置为结尾的最大乘积子数组长度可能为1，那么就是它本身；以【i】位置为结尾为结尾的最大乘积子数组长度可能大于1，结合nums【i】的正负情况，那么以【i】位置为结尾的最大子数组乘积就等于max（dp1【i-1】*nums【i】，dp2【i-1】*nums【i】）相当于三种情况，取三种情况最大值就可以了~ 为了方便表示，我们创建三个变量： int x = nums[i] , y = dp1[i-1]*nums[i] , z = dp2[i-1]*nums[i] 所以状态转移方程为: dp1[i] = max(x,max(y,z))

我们以离【i】位置最近的状态分析状态转移方程，处理dp2表 既然状态表示为：以【i】位置为结尾最小子数组乘积~ ，那么第i个位置肯定在子数组中，那么以【i】位置为结尾的最小乘积子数组长度可能为1，那么就是它本身；以【i】位置为结尾为结尾的最小乘积子数组长度可能大于1，结合nums【i】的正负情况，那么以【i】位置为结尾的最小子数组乘积就等于min（dp1【i-1】*nums【i】，dp2【i-1】*nums【i】）相当于三种情况，取三种情况最小值就可以了~ 为了方便表示，我们创建三个变量： int x = nums[i] , y = dp1[i-1]*nums[i] , z = dp2[i-1]*nums[i] 所以状态转移方程为: dp2[i] = min(x,min(y,z))

3、初始化

我们可以看到，状态转移方程里面有i-1，当i=0的时候显然会出现越界的情况，所以我们需要进行初始化 结合前面如果不想初始化太麻烦，我们可以多申请一些空间，我们可以多申请一个空间，并且把这个空间填写正确的数据保证不影响到后面的结果，我们求数组乘积不希望影响到后面的结果的话，我们知道1乘以任何数等于这个数本身，那么我们让dp1[0]=dp2[0]=1就可以了~ 同时要注意下标映射关系~我们前面的状态转移方程中变量就需要进行修改： int x = nums[i-1] , y = dp1[i-1]*nums[i-1] , z = dp2[i-1]*nums[i-1] 那么我们初始化结果就是 dp1【0】= 1 ；dp2【0】= 1

4、填表顺序

我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前往后,两个dp表一起填

5、返回结果

这里返回结果是最大子数组乘积，而dp1表表示的就是以【i】位置为结尾的最大子数组乘积，整个数组的最大子数组乘积可能是以任意位置结尾的，所以返回dp1表中的最大值就可以了~

代码实现：

//乘积最大子数组
class Solution
{
public:
    int maxProduct(vector<int>& nums)
    {
        //1、创建dp表
        int n = nums.size();
        vector<int> dp1(n + 1);//【i】位置结尾最大乘积子数组
        vector<int> dp2(n + 1);//【i】位置结尾最小乘积子数组

        //2、初始化
        dp1[0] = dp2[0] = 1;

        //3、填表+更新结果
        int ret = INT_MIN;
        for (int i = 1; i < n + 1; i++)
        {
            //创建三个变量——也就是三种情况
            //注意下标映射关系
            int x = nums[i - 1];//本身就是最大乘积
            int y = dp1[i - 1] * nums[i - 1];//nums[i-1]>0是最大乘积
            int z = dp2[i - 1] * nums[i - 1];//nums[i-1]<0是最大乘积

            //最大乘积——三种情况最大值
            dp1[i] = max(x, max(y, z));
            //最小乘积——三种情况最小值
            dp2[i] = min(x, min(y, z));

            //更新结果
            ret = max(ret, dp1[i]);
        }

        //4、返回结果
        return ret;
    }
};

顺利通过~

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

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

题目要求已经十分清晰了，让我们求解乘积为正数的最长子数组长度，我们知道乘积为正数

，可能是负数*负数，也可能是正数*正数，我们这里就需要创建两个dp表来进行表示~

结合动态规划思想分析：

1、状态表示

题目要求：求解乘积为正数的最长连续子数组长度~

结合这里的题目要求+经验+我们的分析，创建两个dp表，一个求乘积为正数最长子数组长度，一个求乘积为负数最长子数组长度： dp1表中的dp1[i]表示为以【i】位置为结尾乘积为正数最长子数组长度~ dp2表中的dp2[i]表示为以【i】位置为结尾乘积为负数最长子数组长度~

2、状态转移方程

我们以离【i】位置最近的状态分析状态转移方程，处理dp1表 既然状态表示为： 以【i】位置为结尾乘积为正数最长子数组长度~，那么第【i】个位置的数可能是正数，也可能是是负数。 如果第【i】个位置的数是正数，正数*正数=正数，那么乘积为正数的最长子数组长度就是以【i-1】个位置为结尾乘积为正数的最长子数组长度+1（也就是加上当前位置）； 如果第【i】个位置的数是负数，负数*负数=正数，那么乘积为正数的最长子数组长度就是以【i-1】个位置为结尾乘积为负数的最长子数组长度+1（也就是加上当前位置），还需要注意的是，当第【i】个位置的数是负数的时候，如果以【i-1】个位置为结尾乘积为负数的最长子数组长度为0就会有问题，就说明只有第【i】个位置本身，而第【i】个位置是负数，是不满足条件的， 所以我们需要先判断以【i-1】个位置为结尾乘积为负数的最长子数组长度是否为0，为0就说明以【i】个位置为结尾乘积为正数的最长子数组长度为0，不为0就等于以【i-1】个位置为结尾乘积为负数的最长子数组长度+1（也就是加上当前位置）~ 所以dp1表状态转移方程为:

如果第【i】个位置的数是正数，dp1[i]=dp1[i-1]+1;

如果第【i】个位置的数是负数，dp1[i]=(dp2[i-1]==0?0:dp2[i-1]+1).

我们以离【i】位置最近的状态分析状态转移方程，处理dp2表 既然状态表示为： 以【i】位置为结尾乘积为负数最长子数组长度~，那么第【i】个位置的数可能是正数，也可能是是负数。 如果第【i】个位置的数是负数，正数*负数=负数，那么乘积为负数的最长子数组长度就是以【i-1】个位置为结尾乘积为正数的最长子数组长度+1（也就是加上当前位置）； 如果第【i】个位置的数是正数，正数*负数=负数，那么乘积为负数的最长子数组长度就是以【i-1】个位置为结尾乘积为负数的最长子数组长度+1（也就是加上当前位置），还需要注意的是，当第【i】个位置的数是正数的时候，如果以【i-1】个位置为结尾乘积为负数的最长子数组长度为0就会有问题，就说明只有第【i】个位置本身，而第【i】个位置是正数，是不满足条件的， 所以我们需要先判断以【i-1】个位置为结尾乘积为负数的最长子数组长度是否为0，为0就说明以【i】个位置为结尾乘积为负数的最长子数组长度为0，不为0就等于以【i-1】个位置为结尾乘积为负数的最长子数组长度+1（也就是加上当前位置）~ 所以dp1表状态转移方程为:

如果第【i】个位置的数是正数，dp2[i]=(dp2[i-1]==0?0:dp2[i-1]+1);

如果第【i】个位置的数是负数，dp2[i]=dp1[i-1]+1.

这里还需要注意的是不考虑第【i】个位置的数是0的时候，因为0乘以任何数等于0，所以不可能为正数，那么以【i】位置为结尾乘积为正数最长子数组长度就等于0~

3、初始化

我们可以看到，状态转移方程里面有i-1，当i=0的时候显然会出现越界的情况，所以我们需要进行初始化 结合前面如果不想初始化太麻烦，我们可以多申请一些空间，我们可以多申请一个空间，并且把这个空间填写正确的数据保证不影响到后面的结果，我们求长度不希望影响到后面的结果的话，我们知道0加任何数等于这个数本身，那么我们让dp1[0]=dp2[0]=1就可以了~ 同时要注意下标映射关系~ 那么我们初始化结果就是 dp1【0】= 0 ；dp2【0】= 0

4、填表顺序

我们这里的逻辑是从前面依次推出后面的，所以填表顺序是从前往后,两个dp表一起填

5、返回结果

这里返回结果是乘积为正数的最大子数组长度，而dp1表表示的就是以【i】位置为结尾的乘积为正数的最大子数组长度，整个数组的乘积为正数的最大子数组长度可能是以任意位置结尾的，所以返回dp1表中的最大值就可以了~

代码实现：

//乘积为正数的最长子数组长度
class Solution
{
public:
    int getMaxLen(vector<int>& nums)
    {
        //1、创建dp表
        int n = nums.size();
        vector<int> dp1(n + 1);//以【i】位置为结尾乘积为正数最长子数组长度~
        vector<int> dp2(n + 1);//以【i】位置为结尾乘积为负数最长子数组长度~
        //默认全部初始化为0
        //2、初始化
       // dp1[0]=dp2[0]=0;//可写也可以不写
        //3、填表+更新结果
        int ret = 0;
        for (int i = 1; i < n + 1; i++)
        {
            //注意下标映射关系
            if (nums[i - 1] > 0)//当前位置为正数
            {
                dp1[i] = dp1[i - 1] + 1;
                dp2[i] = (dp2[i - 1] == 0 ? 0 : dp2[i - 1] + 1);
            }
            else if (nums[i - 1] < 0)//当前位置为负数
            {
                dp1[i] = (dp2[i - 1] == 0 ? 0 : dp2[i - 1] + 1);
                dp2[i] = dp1[i - 1] + 1;
            }
            ret = max(ret, dp1[i]);
        }

        //4、返回结果
        return ret;
    }
};

顺利通过~