首页 > 代码库 > 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.
思路：类似最大和连续子序列那样，不过除了记录最大乘积，我们还要记录最小的乘积。这里我分三种情况：
1.A[i]>0。
2.A[i]<0。p[i].max=Max(p[i-1].min*A[i],A[i]);也就是看看前i-1项的最小值是不是负数，若是负数,则p[i].max=p[i-1]*A[i]（负负得正）；若不是负数，则p[i]=A[i]。
3.若A[i]=0，则以0为结尾的序列的乘积的最大值和最小值一定都是0。
代码：
class Solution {private:struct pro{ int max; int min;};public: int Max(int a,int b){ return a>b?a:b; } int Min(int a,int b){ return a<b?a:b; } int maxProduct(int A[], int n) { struct pro p[n]; p[0].max=A[0]; p[0].min=A[0]; for (int i=1;i<n;++i) { if(A[i]>0){ p[i].max=Max(p[i-1].max*A[i],A[i]); p[i].min=Min(p[i-1].min*A[i],A[i]); } else if(A[i]<0){ p[i].max=Max(p[i-1].min*A[i],A[i]); p[i].min=Min(p[i-1].max*A[i],A[i]); } else{ p[i].max=0; p[i].min=0; } } int res=p[0].max; for (int i=1;i<n;++i) { if(p[i].max>res) res=p[i].max; } return res; }};
Maximum Product Subarray(最大连续乘积子序列)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。