首页 > 代码库 > Maximum Product Subarray （3）
Maximum Product Subarray （3）
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.
标签
数组 dp
联想到最大连续子数组和O(n)的dp代码，我敏锐的感觉到这个求最大连续字数组乘积的问题同样也可以做到O(n).先贴出求最大连续字数组和的代码：
1 int max_sum(int a[],int n){ 2 int b,sum; 3 sum=a[0];//这样就能应对所有特殊情况了，例如首项为负数 4 b=0; 5 int i; 6 for(i=0;i<n;i++){ 7 if(b<0)//如果连续项的和小于0，那么要将前面项的和抛弃 8 b=a[i]; 9 else10 b+=a[i];//反之，继续求连续项的和11 if(b>sum)//保证sum是最大的连续项的和12 sum=b;13 14 }15 return sum;//返回最大子数组和16 }
那么怎么样举一反三，解决好这个问题呢？
根据dp的思路，我们先思考一下我们需要用于存储的局部变量的个数。一个是显然不够的。一个连续最大乘积的可能源于上一个最大的乘积，也可能来自于最小的那个乘积（值为负值，负负得正了！）,这个开端开好了，下面就顺理成章了！
先贴代码：
1 int max3(int a,int b,int c){ 2 if(a<b) 3 a=b; 4 if(a<c) 5 a=c; 6 return a; 7 } 8 int min3(int a,int b,int c){ 9 if(a>b)10 a=b;11 if(a>c)12 a=c;13 return a;14 }15 class Solution {16 public:17 int maxProduct(int a[], int n) {18 if(n==1)19 return a[0];20 int max;21 int min;22 int i;23 max=min=a[0];24 int end=max;25 for(i=1;i<n;i++){26 int max1;//用临时变量存储max，因为29行调用可能会覆盖max的值，造成30行运算错误27 max1=max;28 29 max=max3(a[i],max1*a[i],min*a[i]);//max取值为a[i],max1*a[i],min*a[i]中最大的30 min=min3(a[i],max1*a[i],min*a[i]);//min取值为a[i],max1*a[i],min*a[i]中最小的31 if(max>end)//保证max存储最大的连续字数组乘积32 end=max;33 }34 35 return end;36 }37 };
Maximum Product Subarray （3）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。