首页 > 代码库 > 算法(8)Maximum Product Subarray

算法(8)Maximum Product Subarray

题目:在一个数组中找到一个子数组,让子数组的乘积最大,比如【2,3,-2,4】返回6

思路:之前自己想到的思路是对于一个int类型的数组,只要负数的个数是偶数,那么乘积肯定是全局乘就可以了,然后对于负数个数是奇数的情况,那么我们就找到最前和最后的一个负数,然后分别计算其前后子数组的乘积就可以了!因为其前后子数组的个数必然是偶数!想到这里还心里窃喜,感觉自己发现了一个莫大的规律,但是分分钟被教做人呢!因为上面红线标注的部分实现起来格外麻烦,但是自己的思维里面还是少了一步!那就是既然你已经想到了要么是从数组头开始,要么从数组尾开始,那么这不直接遍历数组就可以了嘛!【早晨写着写着代码,竟然对后向的乘法的必要性产生怀疑,前向相乘是所有的情况了吗?】那这里就要单独拿出0来说一下了,当一个乘积碰到0的时候,无论多么长的数字,相乘都会是0,前功尽弃!此时就要重置初始乘积了!突然想起来一个数组

2,3,-2,100

这样能找到100吗?如果只是前向的乘积的话,那么肯定是找不到100的,因为有-2这个天堑没办法跨越,但是如果后向的话,相当于从后方包抄了!

正确理解这种数组的结构吧!

算法(8)Maximum Product Subarray