算法leetcode

最大子数组乘积

字数统计: 2.2k字   |   阅读时长: 9分
, ,

摘要: 最大子数组乘积，最大子数组和的一个变种问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到这个问题有三种解法，都非常主流，并且各个方法都有它适用的变种问题。

在文章 环形数组上的最大子数组和 和文章 最大子矩阵和 中，我们看了两类最直接的变种：第一个是把数组变成环形数组，那道题的重点是怎样把环形数组上的问题转换为普通数组上的问题。只要完成了正确的转换，就可以套用普通数组上我们已经知道的解法；第二个是把数组变成矩阵，那道题的重点是怎样把二维上的问题转化为一维上的问题，只要能正确转化，就可以套用一维上的已知解法来解决。

除了【数组->矩阵】和【数组->环形数组】这类比较直接的变种，对求和的过程增加限制也是一类变种，例如 带大小限制的最大子数组/子矩阵和 中的限制子数组和不大于 k，带长度限制的最大子数组和 中的限制子数组长度不大于 m。

还有一类变种也比较直接，就是把求和这个操作改成乘积。本文我们来处理这个变种。

题目

152. 乘积最大子数组

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

提示:

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

示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

题解

最大子数组乘积与最大子数组和这两个问题，除了求和改成了乘积以外，其他的条件都一模一样。

因此理论上最大子数组和的三个算法: 动态规划、分治、前缀和+单调队列，在最大子数组乘积上均可以使用。

但是乘积比求和复杂的点在于要处理 0 的问题，以及负数的问题。

对于 0，在加法中，加上 0 是使得和不变，但是乘以 0 就直接变成 0 了，这使得单纯地把前缀和改成前缀乘积是不太行的。

对于负数，在加法中，加一个负数只会使得和变小，而乘以一个负数是有可能使得乘积变大的，也就是负数乘以负数变成正数的情况。这使得基于动态规划的算法中，状态转移多了一个来自负数的路径；同样地，基于分治法的算法，在回溯阶段也要处理负数乘以负数变成正数的情况。

考虑到处理 0 和负数方便，动态规划是最适合本题的解法。为了对比方便，我们先回顾一下最大子数组和的动态规划算法，然后给出本题的动态规划算法，最后给出本题的分治法算法。

回顾: 动态规划解决最大子数组和问题

1
2
3
4
5
6
7
8
9
10
11
状态定义：
dp[i] := [0..i] 中，以 nums[i] 结尾的最大子串和

答案:
max(dp[i])

初始化：
dp[0] = nums[0]

状态转移：
dp[i] = nums[i] + max(dp[i - 1], 0)

因为求 dp[i] 时只用到了 dp[i - 1]，所以dp数组可以压缩掉，只用一个变量 sum 维护状态。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int sum = 0; // 以当前位置结尾的最大子串和
        int ans = INT_MIN; // 当前的最大子串和
        for(int i = 0; i < n; ++i)
        {
            sum = nums[i] + max(sum, 0);
            ans = max(ans, sum);
        }
        return ans;
    }
};

算法1: 动态规划

正如前面所说，由于负数乘以负数变为正数可能会更大的情况存在，动态规划的状态转移就有了从负数来的这一支。

因此我们需要在以 nums[i] 结尾的最大子数组乘积 dp_max[i] 之外，再维护一个以 nums[i] 结尾的最小子数组乘积 dp_min[i]。

如果 dp_min[i - 1] 是负数，nums[i] 也是负数，那么 dp_min[i - 1] * nums[i] 就是正数了，它有可能就是 dp_max[i]。

完整的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
状态定义：
dp_max[i] := [0..i] 中，以 nums[i] 结尾的最大子串乘积
dp_min[i] := [0..i] 中，以 nums[i] 结尾的最小子串乘积

答案:
max(dp_max[i])

初始化：
dp_max[i] = nums[i]
dp_min[i] = nums[i]

状态转移:
dp_max[i] = max(dp_max[i - 1] * nums[i], nums[i], dp_min[i - 1] * nums[i])
dp_min[i] = min(dp_min[i - 1] * nums[i], nums[i], dp_max[i - 1] * nums[i])

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp_max(n, 0), dp_min(n, 0);
        dp_max[0] = nums[0];
        dp_min[0] = nums[0];
        for(int i = 1; i < n; ++i)
        {
            dp_max[i] = nums[i];
            dp_max[i] = max(dp_max[i], dp_max[i - 1] * nums[i]);
            dp_max[i] = max(dp_max[i], dp_min[i - 1] * nums[i]);
            dp_min[i] = nums[i];
            dp_min[i] = min(dp_min[i], dp_min[i - 1] * nums[i]);
            dp_min[i] = min(dp_min[i], dp_max[i - 1] * nums[i]);
        }
        int ans = dp_max[0];
        for(int i: dp_max) 
            ans = max(ans, i);
        return ans;
    }
};

因为求 dp_min[i] 时只用到了 dp_min[i - 1]、求 dp_max[i] 时只用到了 dp_max[i - 1]，所以 dp_max, dp_min 这两个数组可以压缩掉，只用变量 max_prod 和 min_prod 维护状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int max_prod = nums[0]; // 以当前位置结尾的最大子串乘积
        int min_prod = nums[0]; // 以当前位置结尾的最小子串乘积
        int ans = nums[0]; // 当前的最大子串乘积
        for (int i = 1; i < n; ++i) 
        {
            int new_max_prod = max(max_prod * nums[i], max(nums[i], min_prod * nums[i]));
            int new_min_prod = min(min_prod * nums[i], min(nums[i], max_prod * nums[i]));
            max_prod = new_max_prod;
            min_prod = new_min_prod;
            ans = max(max_prod, ans);
        }
        return ans;
    }
};

算法2: 分治

对于左闭右开区间 [left, right)，它的长度为 length = right - left。

令 mid = (length + 1) / 2 + left，可以得到两个左闭右开的子区间 [left, mid), [mid, right)。

[left, right) 上乘积最大的子串的位置有三种情况：

  1. 完全在左半区间 [left, mid) ：直接递归，需要 $O(\log N)$ 次
  2. 完全在右半区间 [mid, right)：直接递归，需要 $O(\log N)$ 次
  3. 两个半区间各占一部分：在递归的回溯阶段做，这部分需要O(N)

三种情况的最大子串乘积分别记为 left_result, right_result, mid_result。max(left_result, right_result, mid_result) 就是 [left, right) 上的最大子串乘积。递归终止条件为 length = 1。

下面说一下两个半区间各占一部分的答案 mid_result 的求法。

首先求左边这一半区间 [left, mid) 上以 nums[mid - 1] 为结尾的子数组的最大乘积 max_left_prod 与最小乘积 min_left_prod；

然后求右边这一半区间 [mid, right) 上以 nums[mid] 为开头的子数组的最大乘积 max_right_prod 与最小乘积 min_right_prod。

正如前面我们提到的，要处理两个负数相乘变成正数可能会更大的情况，mid_result 有两种可能得情况，一个是 max_left_prod * max_right_prod，另一个是 min_left_prod * min_right_prod。

分治法的时间复杂度为 $O(N\log N)$，不如动态规划的 O(N)。

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
36
37
38
39
40
41
42
43
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        return solve(nums, 0, n);
    }

    int solve(const vector<int>& nums, int left, int right)
    {
        // [left, right)
        int length = right - left;

        if(length == 1)
            return nums[left];

        int mid = (length + 1) / 2 + left;
        int left_result = solve(nums, left, mid);
        int right_result = solve(nums, mid, right);

        // 横跨两个区间的候选答案 mid_result 一定包含 nums[mid] 和 nums[mid - 1]
        int right_prod = nums[mid];
        int max_right_prod = right_prod;
        int min_right_prod = right_prod;
        for(int i = mid + 1; i < right; ++i)
        {
            right_prod *= nums[i];
            max_right_prod = max(max_right_prod, right_prod);
            min_right_prod = min(min_right_prod, right_prod);
        }
        int left_prod = nums[mid - 1];
        int max_left_prod = left_prod;
        int min_left_prod = left_prod;
        for(int i = mid - 2; i >= left; --i)
        {
            left_prod *= nums[i];
            max_left_prod = max(max_left_prod, left_prod);
            min_left_prod = min(min_left_prod, left_prod);
        }
        int mid_result = max(max_left_prod * max_right_prod, min_left_prod * min_right_prod);

        return max(mid_result, max(left_result, right_result));
    }
};
Share