文章目录

1. 1. Maximum Product SubArray
   1. 1.1. 动态规划
   2. 1.2. 数组处理

Maximum Product SubArray

---

问题是求出一个整形矩阵中，最大的连续乘积，比如[2,3,-2,4]，那么将会返回2*3=6。

这道题目我用了两个方法来做，第一个是动态规划，第二个是找出矩阵中的非正数下标。

动态规划

---

我们每次需要记录最大的数，也需要记录最小的负数，因为当一个负数乘以最小的负数时，就会变成最大乘积的提名者。

所以我们的方法是

premax = curmax;

curmax = max(curmax*nums[i],nums[i],curmin*nums[i]);
curmin = min(premax*nums[i],nums[i],curmin*nums[i]);

return max(curmax,curmin);

数组处理

---

仔细观察，我们可以发现乘以0的话，对乘积的大小没有积极影响，所以在遍历容器的时候，可以记录下0和负数的下标，用0来分割连续乘积序列。

接下来处理前一个0到当前0直接的序列，找出这组序列中的所有负数下标，如果下标个数是偶数，那么当前序列的最大值就是它们的乘积；

如果下标个数是奇数，我举个例子来说明：1,2,-3,4,5,-6,7,-8,9,10,11,0,23

我们需要比较序列（以第一个负数来分割）1到2，4到11,（以最后一个负数来分割）1到7,9到11的乘积的最大值。