【Leetcode】【Medium】Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

解题思路:

求连续子串和/积系列,最优的方法是只遍历一遍,实现o(n)的时间复杂度。

思考:

1、对于子序列中连续的正数,那么乘积也是不断的累积,如果遇到了负数,则最大乘积值暂时为前面正数的累积;

如果按照这个思路,只需要记录连续正数乘积最高,即为最大子序列积;那么这样就实现了o(n)的复杂度;

2、但是上面思路忽略了子序列中包含两个负数,负负得正,依然可以成就最大子序列积;

针对这种情况,在遍历的时候,不仅记录乘积最大值,还记录乘积最小值,乘积最小值

原文地址:https://www.cnblogs.com/huxiao-tee/p/4314779.html