leetcode_maximum_product_subarray

发表于

难度：Meidum

看到更好的做法，维护一个当前最大值和当前最小值，如果下一个元素为正，则不变；如果为负，则最大值可能转变为最小值，最小值可能转变为最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maximum = 1;
        int minimum = 1;
        int ret = nums[0];
        for(int i = 0; i < nums.size(); i++)
        {
            int old_maximum = maximum;
            int old_minimum = minimum;
            maximum = max(nums[i],max(nums[i]*old_maximum, nums[i]*old_minimum));
            minimum = min(nums[i],min(nums[i]*old_maximum, nums[i]*old_minimum));
            ret = max(ret,maximum);
        }
        return ret;
    }
};

6ms，超过15.01%

申请同样大的数组ret[]，保存以对应元素结尾的最大乘积。

如果num[i] = 0，则ret[i] = 0
如果nums[i] > 0，则ret[i] = max(nums[i],nums[i]*ret[i-1])
如果nums[i] < 0，则从i-1开始寻找nums中距离i最近的一个小于0的元素，如果寻找的过程中，先找到了0，则ret[i] = 0；如果未寻找到，则ret[i] = nums[i]；如果寻找到了为k，则从k乘到i，如果ret[k-1] > 0，则也要乘进最后的结果，得到ret[i]。

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
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int> ret = nums;
        ret[0] = nums[0];
        int maximum = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] == 0)
                ret[i] = 0;
            else if(nums[i] > 0)
                ret[i] = max(nums[i], ret[i-1]*nums[i]);
            else
            {
                int product = nums[i];
                int j = i-1;
                for(; j >= 0; j--)
                {
                    product *= nums[j];
                    if(product >= 0)
                        break;
                }
                if(product == 0)
                    ret[i] = 0;
                else if(product > 0)
                {
                    if(j-1>=0 && ret[j-1] > 0)
                        product *= ret[j-1];
                    ret[i] = product;
                }
            }
            maximum = max(maximum,ret[i]);
        }
        return maximum;
    }
};

3ms，超过76.77%