【leetcode】动态规划

19. 918 环形子数组的最大和

题目：

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

题目链接

918. 环形子数组的最大和 - 力扣（LeetCode）

文字分析

 代码

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) 
    {
        int sum = 0;
        int n = nums.size();
        vector<int>dp1(n);
        vector<int>dp2(n);
        int Max , Min;
        Max = Min = sum = dp2[0] = dp1[0] = nums[0];
        for(int i = 1;i < n;i++)
        {
            dp1[i] = max(dp1[i - 1] + nums[i],nums[i]);
            dp2[i] = min(dp2[i - 1] + nums[i],nums[i]);
            Max = max(Max,dp1[i]);
            Min = min(Min,dp2[i]);
            sum += nums[i];
        }
        if(Min == sum)
        {
            return Max;
        }
        return Max > sum - Min ? Max : sum - Min;
    }
};

20. 152 乘积最大子数组

题目：

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

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

题目链接

152. 乘积最大子数组 - 力扣（LeetCode）

文字分析

 代码

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

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

题目：

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

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

请你返回乘积为正数的最长子数组长度。

题目链接

1567. 乘积为正数的最长子数组长度 - 力扣（LeetCode）

文字分析

代码

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