题目

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

大意

给定一个数组，求出最大的乘积值。

思路

解题思路：乘法与加法最大差别在于，当前元素的符号具有全局性的作用。

如果当前元素为负，那么连乘到上个元素的最大乘积，再乘以当前元素，就变成负数，甚至可能成为最小乘积。

同样，连乘到上个元素的最小乘积如为负，再乘以当前元素，就变成正数，甚至可能成为最大乘积。

也就是说，当前遍历到的数是一个负数，那么乘以前面的最大元素直接就变成最小元素了。

所以用两个数组 dpmax[] 和dpmin[] 分别记录以i 为最后的乘积的最大值和最小值，然后通过max函数得到最大值。

####　答案

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 len =nums.size();
        if(len==1) return nums[0];
        vector<int> dpmax(len,0);
        vector<int> dpmin(len,0);
        int res =nums[0];
        dpmax[0]=nums[0];
        dpmin[0]=nums[0];
        for(int i=1;i<len;i++)
        {
           dpmax[i] = max(max(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i]),nums[i]);
           dpmin[i] = min(min(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i]),nums[i]);
          //重点在于上面的状态转移方程，当前的最大值可能是前面的最大值乘以当前的数字
          //也可能是前面的最小值（比如是一个负数）乘以当前的负数，变成最大值。
          //还要和nums[i]比较是有０的情况。
          //同样，当求最小值的时候，当前的最小值可能是前面的最小值（负数）乘当前数，也可能前面的最大值（正数）成为当前数（负数），
          //最后res就等于最大的 dpmax.
           res =max(res,dpmax[i]);
        }
        return res;
    }
};

上面的解法空间复杂度为ｏ(n)观察到状态转移方程中当前状态只和前一个状态有关，所以可能进行保存前一个状态就好，这样就降低了空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//易错解法
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int len =nums.size();
        if(len==1) return nums[0];
        int res =nums[0];
        int dpmax =nums[0];
        int dpmin =nums[0];
        for(int i=1;i<len;i++)
        {
           dpmax = max(max(dpmax*nums[i],dpmin*nums[i]),nums[i]);
          	//错误的原因就在于 dpmax在得到后没有进行保存，本来下面的dpmax是前一个数的dpamx,但是经过上面的计算后就有了新的ｄｐｍａｘ,下面计算ｄｐｍｉｎ的时候直接用了新的ｄpmax进行计算，所以错了。
           dpmin = min(min(dpmax*nums[i],dpmin*nums[i]),nums[i]);
           res = max(res,dpmax);
        }
        return res;
    }
};
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 len =nums.size();
        if(len==1) return nums[0];
        int res =nums[0];
        int dpmax =nums[0];
        int dpmin =nums[0];
        int mmax;
        int mmin;
        for(int i=1;i<len;i++)
        {
           mmax = max(max(dpmax*nums[i],dpmin*nums[i]),nums[i]);
           mmin = min(min(dpmax*nums[i],dpmin*nums[i]),nums[i]);
           dpmax=mmax;
           dpmin=mmin;
           res = max(res,mmax);
        }
        return res;
    }
};