题目描述

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续

子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

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

示例 1:

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

具体见题目详解。

算法思路

emmm这道题目我看得出来是一道dp的题目，但是我最后没做出来，看了官方题解跟大神题解后真感觉算法也是等级森严……

思路借鉴

方法1-动态规划

先看一下官方题解，主要使用的思路就是动态规划，但是跟以往我做的动态规划不同的就是：虽然这个题目求的是最大乘积子数组，但是我们还需要维护一个最小乘积子数组，为什么呢？因为数组中存在负数，如果当前位置为正数，我们肯定希望他的前一部分越大越好，这样才能得到更大的乘积；但是如果当前位置是一个负数，那么我们需要他的前一部分乘积越小越好，这样才能负负得正。结合动态规划的思想，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector <long> maxF(nums.begin(),nums.end()), minF(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); ++i) {
            maxF[i] = max(maxF[i - 1] * nums[i], max((long)nums[i], minF[i - 1] * nums[i]));
            minF[i] = min(minF[i - 1] * nums[i], min((long)nums[i], maxF[i - 1] * nums[i]));
            if(minF[i]<INT_MIN) {
                minF[i]=nums[i];
            }
        }
        return *max_element(maxF.begin(), maxF.end());
    }
};

时间复杂度和空间复杂度都是O(n)，运行结果就不演示了。

方法2-贪心

这个思路真的震惊我了，属于是不学算法的人（比如我）这辈子都很难想出来，原文在这，先看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int product = 1, n = nums.size();
        int maxnum = nums[0];

        for (int i = 0; i < n; i++) {
            product *= nums[i];
            maxnum = max(maxnum, product);
            if (nums[i] == 0) {
                product = 1;
            }
        }
        product = 1;
        for (int i = n - 1; i >= 0; i--) {
            product *= nums[i];
            maxnum = max(maxnum, product);
            if (nums[i] == 0){
                product = 1;
            }
        }
        return maxnum;
    }
};

我使用评论区大佬的原话帮助理解：“主要思路是贪心。这个使用了一个结论，一个不包含0的整数序列的连续乘积最大值，一定以起点开始或者以终点结束。使用反证法可以证明，如果连续乘积最大值不以起点开始也不以终点结束，也就是说，结果序列两边都有非0整数。分类讨论：

  1. 如果连续乘积最大值为正，那么结果序列左右两边应该异号，否则可以向两边扩展，而如果两边异号，那么一定存在一边为正，也可以继续扩展，与假设矛盾。
  2. 如果连续乘积最大值为负，那么结果序列两边一定同号，否则可以向两边扩展，如果同负，那么乘以任意一个负数都会让乘积变大，如果同正，那么任意一个正数都大于这个负数的连续乘积最大值。

综上，不以起点开始且不以终点结束的序列，一定不是最大的连续乘积”。

如果把上面这段话看懂，那么这个代码就很容易理解，我们可以举个例子，比如[2, 3, 4, -2]，正向遍历得到的最大值就是24，反向遍历因为负数在最开始所以是-8。但是绝对不可能是-2或者3 * 4 = 12：如果是-2,那么根据如果连续乘积最大值为负，那么结果序列两边一定同号，否则可以向两边扩展，......，如果同正，那么任意一个正数都大于这个负数的连续乘积最大值。那么肯定能得到2 * 3 * 4 = 24；如果是12，那么根据如果连续乘积最大值为正，那么结果序列左右两边应该异号，否则可以向两边扩展，而如果两边异号，那么一定存在一边为正，也可以继续扩展，与假设矛盾。也一定可以向2这边拓展。整体思路真的非常新奇，不看评论区大佬的分析也难以理解……