本文共 843 字，大约阅读时间需要 2 分钟。

对于Product Subarray，要考虑到一种特殊情况，即负数和负数相乘：如果前面得到一个较小的负数，和后面一个较大的负数相乘，得到的反而是一个较大的数，如{2，-3，-7}，所以，我们在处理乘法的时候，除了需要维护一个局部最大值，同时还要维护一个局部最小值，由此，可以写出如下的转移方程式：

max_copy[i] = max_local[i]
max_local[i + 1] = Max(Max(max_local[i] * A[i], A[i]),  min_local * A[i])

min_local[i + 1] = Min(Min(max_copy[i] * A[i], A[i]),  min_local * A[i])

max_local[i + 1]表示已下标i+1结尾的连续字数组的最大乘积

class Solution {public:    int maxProduct(vector
    
     & nums) {        int len = nums.size();        if(len == 0) return -1;        int res = nums[0];        int dpmax = nums[0] , dpmin = nums[0];        for(int i = 1; i < len; i++){            int tmpmax = max(max(dpmax * nums[i],nums[i]),dpmin * nums[i]);            dpmin = min(dpmax * nums[i],min(dpmin * nums[i],nums[i]));            dpmax = tmpmax;            if(dpmax > res) res = dpmax;        }        return res;    }};
    

转载地址：http://vmspi.baihongyu.com/