首页 > 代码库 > Maximum Product Subarray
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.
分析：我们可以通过下面的思路分析这道题，对于乘法运算array中的整数值可以分三类：0、正数、负数。当连续的subarray中包含0，则乘积为0，所以首先我们可以把0元素作为分隔符将array分成一系列subarray（当然代码实现并非先将array分成一系列subarray，这里这样表达便于理解）。然后在每个不含0的subarray中，我们可以这样考虑，如果第一个元素到当前元素共有偶数个负数，那么此subarray中最大成绩为从第一个元素到当前元素的乘积；如果第一个元素到当前元素共有奇数个负数，那么此subarray的最大乘积将在原来的max_product和此subarray第一个负数之后到当前元素段乘积中产生。实现算法是，遇到0可以更新一些标记量，从而可以使上述方法在O(n)时间复杂度完成。代码如下：
class Solution {public: int maxProduct(int A[], int n) { int maxP = INT_MIN; int from_start = 1, from_first_neg = 1; int neg_count = 0; for(int i = 0; i < n; i++){ if(A[i] == 0){ maxP = max(maxP,0); from_start = 1; from_first_neg = 1; neg_count = 0; }else{ from_start *= A[i]; if(neg_count > 0) from_first_neg *= A[i]; if(A[i] < 0) neg_count++; if(neg_count%2 == 0 || (neg_count == 1 && A[i] < 0))maxP = max(maxP,from_start); else if(neg_count > 0) maxP = max(maxP, from_first_neg); } } return maxP; }};
Maximum Product Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。