Cinte's Leetcode Record
0%

152. Maximum Product Subarray

Posted on Edited on In Disqus:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

152. Maximum Product Subarray

仿kadane算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxSoFar = nums[0];
        
        int maxEndHere = nums[0];
        int minEndHere = nums[0];
        for(auto i = nums.begin() + 1; i != nums.end(); ++i)
        {
            int num = *i;
            if(num < 0)
                swap(maxEndHere, minEndHere); // 如果num<0，那么乘了之后，他们势必会翻转，max如果是大的，乘后就会变小
            
            maxEndHere = max(num, maxEndHere * num); // 假如还不如现在的大，那么你也没用啊，我不如前面的不乘了
            minEndHere = min(num, minEndHere * num); //
            
            maxSoFar = max(maxEndHere, maxSoFar);
        }
        return maxSoFar;
    }
};
另一种思路
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 maxNum{ nums[0] };
        int product{ 1 };
        for(auto i = nums.begin(); i != nums.end(); ++i)
        {
            maxNum = max(maxNum, product *= *i);
            if(!*i) product = 1;
        }
        product = 1;
        for(auto i = nums.end() - 1; i != nums.begin(); --i)
        {
            maxNum = max(maxNum, product *= *i);
            if(!*i) product = 1;
        }
        return maxNum;
    }
};
review
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 ret = nums[0];
        int curLR = 1;
        int curRL = 1;
        for(int i = 0, j = nums.size() - 1; i < nums.size(); ++i, --j)
        {
            ret = max(ret, max(curLR *= nums[i], curRL *= nums[j]));
            if(nums[i] == 0)
                curLR = 1;
            if(nums[j] == 0)
                curRL = 1;
        }
        return ret;
    }
};

当负数的个数为偶数时，全乘起来就是最大，为奇数时，需要抛弃一个
每次的乘法，最大的乘积受到最后一个负数的限制

review
当负数个数为偶数且中间没有0，那么无论左到右还是右到左都会遍历到。

抛开此外，可以观察到分界线为0，每一块被0分开的没0区域都表示一个乘积，当这一个区域没有负数或者负数个数为偶数，那么无论左到右还是右到左都会遍历到。当为奇数，那么以其中一个负数为分界线将分成左右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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ret = INT_MIN;
        int begin = 0;
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] == 0)
            {
                ret = max(ret, helper(nums, begin, i));
                begin = i + 1;
            }
        }
        ret = max(ret, helper(nums, begin, n));
        if(begin != 0 && ret < 0)
            ret = 0;
        return ret;
    }
private:
    int helper(vector<int>& nums, int start, int end)
    {
        int ret = INT_MIN;
        int cur = 1;
        for(int i = start; i < end; ++i)
        {
            cur *= nums[i];
            ret = max(ret, cur);
        }

        cur = 1;
        for(int i = end - 1; i >= start; --i)
        {
            cur *= nums[i];
            ret = max(ret, cur);
        }
        return ret;
    }
};