算法沉淀——动态规划之子数组、子串系列（上）（leetcode真题剖析）

01.最大子数组和

题目链接：https://leetcode.cn/problems/maximum-subarray/、

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

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

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
1
2
3

示例 2：

输入：nums = [1]
输出：1
1
2

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23
1
2

提示：

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

**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

思路

1. 状态表示：
   • 使用「经验 + 题目要求」定义线性动态规划的状态表示。
   • 选择以「某个位置为结尾」的方式，结合「题目要求」，定义状态表示：dp[i] 表示以 i 位置元素为结尾的「所有子数组」中和的最大和。
2. 状态转移方程：
   • 将 dp[i] 的所有可能分为两种情况：子数组的长度为 1 或子数组的长度大于 1。
   • 如果子数组长度为 1，则 dp[i] = nums[i]。
   • 如果子数组长度大于 1，则 dp[i] 应该等于以 i-1 为结尾的「所有子数组」中和的最大值再加上 nums[i]，即 dp[i-1] + nums[i]。
   • 转移方程为 dp[i] = max(nums[i], dp[i-1] + nums[i])。
3. 初始化：
   • 在最前面加上一个「辅助结点」，用于初始化。辅助结点的值要保证后续填表是正确的，因此设 dp[0] = 0。
   • 辅助结点的存在需要注意下标的映射关系。
4. 填表顺序：
   • 根据「状态转移方程」，填表顺序为「从左往右」。
5. 返回值：
   • 状态表 dp 表示以 i 为结尾的所有子数组的最大值，但最大子数组和的结尾是不确定的。因此，返回整个 dp 表中的最大值。

代码

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

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

        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

02.环形子数组的最大和

题目链接：https://leetcode.cn/problems/maximum-sum-circular-subarray/

给定一个长度为 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 。

示例 1：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
1
2
3

示例 2：

输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
1
2
3

示例 3：

输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
1
2
3

提示：

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

思路

这个问题与「最大子数组和」的区别在于需要考虑数组首尾相连的情况。结果可能有两种情况：一是在数组的内部，包括整个数组；二是在数组首尾相连的一部分上。

1. 对于第一种情况，按照「最大子数组和」的方法得到结果，记为 fmax。
2. 对于第二种情况，分析得出，第二种情况的最大和应等于数组总和减去最小子数组和。其中，最小子数组和表示为 gmin。
3. 两种情况下的最大值即为所求结果。然而，需要特殊处理数组内全部为负数的情况，因为直接比较两者的最大值可能会得到 0。这种情况下，实际结果应为数组内的最大值。
4. 对于「最小子数组和」的求解过程与「最大子数组和」相同，使用 f 表示最大和，g 表示最小和。
5. 返回值：先找到 f 表的最大值 fmax；找到 g 表的最小值 gmin；统计所有元素的和 sum；返回 sum == gmin ? fmax : max(fmax, sum - gmin)。

代码

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

        int fmax=INT_MIN,gmin=INT_MAX,sum=0;
        for(int i=1;i<=n;++i){
            int x=nums[i-1];
            sum+=x;
            f[i]=max(x,x+f[i-1]);
            fmax=max(fmax,f[i]);
            g[i]=min(x,x+g[i-1]);
            gmin=min(gmin,g[i]);
        }

        return sum==gmin ? fmax : max(fmax,sum-gmin);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

03.乘积最大子数组

题目链接：https://leetcode.cn/problems/maximum-product-subarray/

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

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

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

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
1
2
3

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
1
2
3

提示:

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

思路

这道题类似于「最大子数组和」，但需要考虑乘积而非和。定义两个状态数组 f[i] 和 g[i] 分别表示以 i 为结尾的所有子数组的最大乘积和最小乘积。

1. 状态表示：
   • f[i] 表示以 i 为结尾的所有子数组的最大乘积。
   • g[i] 表示以 i 为结尾的所有子数组的最小乘积。
2. 状态转移方程：
   • 对于 f[i]，需要考虑三种情况：子数组长度为 1，子数组长度大于 1 且 nums[i] > 0，子数组长度大于 1 且 nums[i] < 0。
   • 综上，f[i] = max(nums[i], max(nums[i] * f[i - 1], nums[i] * g[i - 1]))。
   • 对于 g[i]，同样考虑三种情况。
   • 综上，g[i] = min(nums[i], min(nums[i] * f[i - 1], nums[i] * g[i - 1]))。
3. 初始化：
   • 在最前面加上一个辅助结点，并设置 f[0] = g[0] = 1。
4. 填表顺序：
   • 从左往右，两个表一起填。
5. 返回值：
   • 返回 f 表中的最大值。

代码

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

        f[0]=g[0]=1;
        int ret=INT_MIN;
        for(int i=1;i<=n;++i){
            int x=nums[i-1],y=f[i-1]*nums[i-1],z=g[i-1]*nums[i-1];
            f[i]=max(x,max(y,z));
            g[i]=min(x,min(y,z));
            ret=max(ret,f[i]);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

题目链接：https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/

定一个整数数组nums，找到其中所有元素的乘积为正的子数组的最大长度。

数组的子数组是从该数组中取出的零个或多个值的连续序列。

返回具有正积的子数组的最大长度。

示例1：

输入： nums = [1,-2,-3,4]
输出： 4
解释：数组 nums 的乘积已经为 24。
1
2
3

示例2：

输入： nums = [0,1,-2,-3,-4]
输出： 3
解释：具有正积的最长子数组是 [1,-2,-3]，其积为 6。
请注意，我们不能在子数组中包含 0，因为这会使乘积为 0，而 0 不是正数。
1
2
3
4

示例3：

输入： nums = [-1,-2,-3,0,1]
输出： 2
解释：具有正积的最长子数组是 [-1,-2] 或 [-2,-3]。
1
2
3

限制条件：

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

思路

1. 状态表达： 定义两个动态规划数组 f 和 g，其中：

• f[i] 表示以 i 为结尾的所有子数组中，乘积为正数的最长子数组长度。
• g[i] 表示以 i 为结尾的所有子数组中，乘积为负数的最长子数组长度。

2. 状态转移方程： 对于 f[i]，根据当前元素 nums[i] 的值，分三种情况讨论：

• 如果 nums[i] = 0，说明当前子数组的乘积为零，所以 f[i] = 0。

• 如果 nums[i] > 0，说明当前子数组的乘积为正数，直接找到 f[i - 1] 的值并加一，即 f[i] = f[i - 1] + 1。

• 如果

  nums[i] < 0
  1

  ，需要根据

  g[i - 1]
  1

  的值来判断：

  • 如果 g[i - 1] 为零，表示以 i - 1 为结尾的最长负数子数组不存在，所以 f[i] = 0。
  • 如果 g[i - 1] 不为零，表示以 i - 1 为结尾的最长负数子数组存在，此时 f[i] = g[i - 1] + 1。

对于 g[i]，也分三种情况讨论：

• 如果 nums[i] = 0，说明当前子数组的乘积为零，所以 g[i] = 0。

• 如果 nums[i] < 0，说明当前子数组的乘积为负数，直接找到 f[i - 1] 的值并加一，即 g[i] = f[i - 1] + 1。

• 如果

  nums[i] > 0
  1

  ，需要根据

  g[i - 1]
  1

  的值来判断：

  • 如果 g[i - 1] 为零，表示以 i - 1 为结尾的最长负数子数组不存在，所以 g[i] = 0。
  • 如果 g[i - 1] 不为零，表示以 i - 1 为结尾的最长负数子数组存在，此时 g[i] = g[i - 1] + 1。

3. 初始化： 在数组最前面加上一个辅助结点，设置 f[0] = g[0] = 0。

4. 填表顺序： 从左往右遍历数组，同时填充 f 和 g 两个动态规划数组。

5. 返回值： 返回 f 数组中的最大值，即为最终结果。

代码

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n+1);
        vector<int> g(n+1);
        int ret=INT_MIN;
        for(int i=1;i<=n;++i){
            if(nums[i-1]>0){
                f[i]=f[i-1]+1;
                g[i]=g[i-1]==0?0:g[i-1]+1;
            }else if(nums[i-1]<0){
                f[i]=g[i-1]==0?0:g[i-1]+1;
                g[i]=f[i-1]+1;
            }
            ret=max(ret,f[i]);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20