Description

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.

 

Solution

求子序列可能产生的最大乘积。

由于是要求某个乘积，数字0会破坏其它数字，所以对零要进行特殊处理。这里的做法是把0当成是所给的数组的分隔符，分别求被0分隔的每段数组中的最大值，最后合成一个最大值，但由于有0的分隔，最终的结果不应该小于0。比如当每段数组的最大值都是负数时，最终结果就是0。

这样问题就转化为对于不包含0的数组，求其子序列可能产生的最大乘积。

对于每段数组的最大乘积，由于已经不再包含0，即使因数中有1或-1，最终也不会减小总乘积的绝对值。所以对于每段数组，所有的数相乘即是有最大绝对值的乘积，但这个乘积可能为负，接下来是需要去掉一个负数因数使结果变为正数即可。

当每段的总乘积为负时，需要在因数中剔除1个负数就可以让乘积变成正数。由于负数不一定在数组的两端而子序列必须是连续的，因此剔除它时也会同时损失一部分正数。由于只需要剔除1个负数，所以只需要选择从左或右的一边开始剔除，直到第一个负数，左右两种方案损失更小的一种的结果即是返回值。（但有一种特殊情况：整段数组只有1个数，并且它是负数，此时应该就以该值为该段数组的“最大乘积”的返回值。）

 

Code

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
    int fun(vector<int>& nums, int p1, int p2)
    {
        if(p2 - p1 == 1) return nums[p1];
        int neg_cnt = 0;
        int product = 1;
        for(int i = p1; i < p2; i++)
        {
            product *= nums[i];
            if(nums[i] < 0) neg_cnt++;
        }
        if(neg_cnt == 0) return product;
        if(neg_cnt % 2)
        {
            int pro_left = 1, pro_right = 1;
            for(int i = p1; ; i++)
            {
                pro_left *= nums[i];
                if(nums[i] < 0)
                {
                    break;
                }
            }
            for(int i = p2 - 1; ; i--)
            {
                pro_right *= nums[i];
                if(nums[i] < 0)
                {
                    break;
                }
            }
            return pro_left > pro_right ? product / pro_left : product / pro_right;
        }
        else
        {
            return product;
        }
    }
    int maxProduct(vector<int>& nums)
    {
        int nsize = nums.size();
        int ret = INT_MIN;
        if(nsize == 0) return ret;
        int p1 = 0,p2 = 0;
        while(true)
        {
            if(nums[p1] == 0)
            {
                if(ret < 0) ret = 0;
            }
            while(p1 < nsize && nums[p1] == 0) p1++;
            if(p1 == nsize) break;
            p2 = p1;
            while(p2 < nsize && nums[p2] != 0) p2++;
            printf("[%d %d)\n", p1, p2);
            int funret = fun(nums, p1, p2);
            if(funret > ret) ret = funret;
            p1 = p2;
            if(p1 == nsize) break;
        }
        return ret;
    }
};