首页 > 代码库 > 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.
此题要求是要在一个无需的数组找出一个乘积最大的连续子数组
例如[2,3,-2,4]，因为可能有负数，可以设置两个临时变量mint和maxt，mint存储遇到负数之后相乘变小的乘积，maxt用来存储大的乘积。
比如2*3=6，此时，mint = maxt = 6,当下次遇到-2时，mint = maxt = -12，此时乘积-12小于-2，则应使maxt = -2。为避免下个数还是负数，应使mint不变，若下次遇到负数，则乘积比maxt大，然后交换……
具体看代码：
1 public class Solution { 2 public int maxProduct(int[] A) { 3 int n = A.length; 4 int mint = 1; 5 int maxt = 1; 6 7 int maxvalue = http://www.mamicode.com/A[0]; 8 for(int i = 0 ; i < n ; i++){ 9 if(A[i] == 0){10 mint = 1;11 maxt = 1;12 if(maxvalue < 0)13 maxvalue = http://www.mamicode.com/0;14 }else{15 int curmax = maxt * A[i];16 int curmin = mint * A[i];17 18 maxt = curmax > curmin ? curmax : curmin;19 mint = curmax > curmin ? curmin : curmax;20 21 if(maxt < A[i])22 maxt = A[i];23 24 if(mint > A[i])25 mint = A[i];26 27 if(maxt > maxvalue)28 maxvalue =http://www.mamicode.com/ maxt;29 }30 }31 32 return maxvalue;33 34 }35 }
Maximum Product Subarray 最大连续乘积子集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。