Problem: 152. 乘积最大子数组

题目描述

思路

1.初始化：首先，我们创建两个数组maxNum和minNum，并将它们初始化为输入数组nums。这两个数组用于存储到当前位置的最大和最小乘积。我们还需要一个变量maxProduct来存储全局的最大乘积，我们将其初始化为数组的第一个元素。
2.状态转移：然后，我们从数组的第二个元素开始遍历数组。对于每一个元素，我们有三种选择：

2.1.我们可以选择与前一个位置的最大乘积相乘，得到新的最大乘积。
2.2.我们可以选择与前一个位置的最小乘积相乘，可能得到新的最大乘积（当当前元素为负数时）。
2.3.我们可以选择只取当前元素，即抛弃前面的元素，开始新的子数组（当前面的元素乘积为负数时）。 我们需要对这三种选择取最大值，作为新的最大乘积。同样，我们也需要对这三种选择取最小值，作为新的最小乘积。

3.更新全局最大乘积：在每一步中，我们都需要更新全局最大乘积maxProduct。我们只需要比较maxProduct和当前的最大乘积，取其中的最大值即可。

复杂度

时间复杂度:

$O(n)$；其中$n$为数组nums的长度

空间复杂度:

$O(n)$

Code

class Solution {
public:
    /**
     * Dynamic programming
     * 
     * @param nums Given array
     * @return int
     */
    int maxProduct(vector<int>& nums) {
        vector<int> maxNum(nums);
        vector<int> minNum(nums);
        int maxProduct = INT_MIN;
        for (int i = 1; i < nums.size(); ++i) {
            maxNum[i] = max(maxNum[i - 1] * nums[i], max(nums[i], minNum[i - 1] * nums[i]));
            minNum[i] = min(minNum[i - 1] * nums[i], min(nums[i], maxNum[i - 1] * nums[i]));
        }
        for (int i = 0; i < nums.size(); ++i) {
            maxProduct = max(maxProduct, maxNum[i]);
        }
        return maxProduct;
    }
};