152. 乘积最大子数组

题目

暴力左右指针

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0];
        for (int i = 0; i < nums.size(); i ++) {
            int tmp = nums[i];
            res = max(res, tmp);
            for (int j = i + 1; j < nums.size(); j ++) {
                tmp *= nums[j];
                res = max(res, tmp);
            }
        }

        return res;
    }
};

动态规划

思路：动态规划，维护两个状态 imax 和 imin，分别表示以当前元素结尾的最大乘积和最小乘积。因为负数会导致乘积变小，所以当遇到负数时，需要交换 imax 和 imin 的值。然后更新 imax 和 imin，并更新结果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0];
        int imax = res, imin = res;

        for (int i = 1; i < nums.size(); i ++) {
            if (nums[i] < 0) swap(imax, imin);
            imax = max(nums[i], imax * nums[i]);
            imin = min(nums[i], imin * nums[i]);
            res = max(res, imax);
        }

        return res;
    }
};