蓝桥杯刷题_day10

最大子数组和

【题目描述】
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

【输入样例】

nums = [-2,1,-3,4,-1,2,1,-5,4]

【输出样例】

6

【数据规模与约定】

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

【解题思路】
这道题可以使用动态规划来解决。我们可以定义一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最大子数组和。
对于每个位置 i，我们有两种选择：

1. 将 nums[i] 加入到前面的子数组中，即 dp[i] = dp[i-1] + nums[i]。
2. 从 nums[i] 开始一个新的子数组，即 dp[i] = nums[i]。

我们取这两种情况的最大值作为 dpi 的值。最后，整个数组的最大子数组和就是 dp 数组中的最大值。
状态转移方程：
dp[i] = max(dp[i-1] + nums[i], nums[i])
初始状态：
dp[0] = nums[0]
最终结果：
max(dp[0], dp[1], …, dp[n-1])

时间复杂度：O(n)
空间复杂度：O(n)，可以优化为 O(1)，因为只需要保存上一个状态的值

【C++程序代码】

1. 暴力解法

//正确  但是超出时间限制
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        int max_num = -0x3f3f3f3f;

        for (int i = 0; i < n; i++)
        {
            int tmp = 0;
            for (int j = i; j < n; j++)
            {
                max_num = max(max_num, tmp += nums[j]);
            }
        }

        return max_num;
    }
};

2. 动态规划

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        vector<int> dp(n, -0x3f3f3f3f);
        dp[0] = nums[0];
        int ret = dp[0];
        for (int i = 1; i < n; i++)
        {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            ret = max(dp[i], ret);
        }

        return ret;
    }
};

环形子数组的最大和

【题目描述】
给定一个长度为 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 。

【输入样例】

nums = [1,-2,3,-2]

【输出样例】

3

【数据规模与约定】

• n == nums.length
• 1 <= n <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104​​​​​​​

【解题思路】
这道题是最大子数组和的变种，因为数组是环形的，所以我们需要考虑两种情况：

1. 最大子数组在数组的中间部分，不包括首尾相连的部分。这种情况可以直接使用最大子数组和的解法求解。
2. 最大子数组包括首尾相连的部分。这种情况可以转化为求数组中非最小子数组的和，即总和减去最小子数组的和。
   所以，我们可以先求出数组的总和 sum，然后求出数组的最小子数组和 minsum。最后，结果就是 max(maxsum, sum - minsum)，其中 maxsum 是数组的最大子数组和。
   需要注意的是，如果数组的所有元素都是负数，那么最小子数组和就等于总和，此时结果就是最大子数组和。
   时间复杂度：O(n)
   空间复杂度：O(1)

【C++程序代码】

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();

        vector<int> f(n + 1);
        vector<int> g(n + 1);

        f[0] = 0;
        g[0] = 0;

        int sum = 0;
        int fmax = -0X3F3F3F3F;
        int gmin = 0X3F3F3F3F;
        for (int i = 0; i < n; i++)
        {
            sum += nums[i];
        }

        for (int i = 1; i <= n; i++)
        {
            f[i] = max(nums[i - 1], f[i - 1] + nums[i - 1]);
            if (f[i] > fmax) fmax = f[i];

            g[i] = min(nums[i - 1], g[i - 1] + nums[i - 1]);
            if (g[i] < gmin) gmin = g[i];
        }
        if (sum == gmin)
            return fmax;
        else
            return max(fmax, sum - gmin);
    }
};

乘积最大子数组

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

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

【输入样例】

nums = [2,3,-2,4]

【输出样例】

6

【数据规模与约定】

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数​​​​​​​

【解题思路】
这道题与最大子数组和类似，但是由于乘法的性质，我们需要同时维护最大乘积和最小乘积。

【C++程序代码】

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();

        vector<int> f(n + 1);
        vector<int> g(n + 1);
        f[0] = 1;
        g[0] = 1;

        int fmax = -0x3f3f3f3f;
        for (int i = 1; i <= n; i++)
        {
            f[i] = max({ nums[i - 1], f[i - 1] * nums[i - 1], g[i - 1] * nums[i - 1] });
            g[i] = min({ nums[i - 1], g[i - 1] * nums[i - 1], f[i - 1] * nums[i - 1] });
            if (f[i] > fmax)
            {
                fmax = f[i];
            }
        }
        return fmax;
    }
};