首页 > 代码库 > [LeetCode] 152. Maximum Product Subarray Java
[LeetCode] 152. Maximum Product Subarray Java
题目：
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.
题意及分析：给出一个数组，求出乘积最大的子数组。这道题可以使用动态规划的方法求解，我使用两个数组posRes和nonPosRes分别用来保存到当前元素的最大的正乘积和最小的负乘积。分析可知，除了只有一个负数的情况下，子数组最大乘积肯定大于等于1。所以对于数组第i-1个元素nums[i-1]，我们可以看出到当前这个数的最大乘积可能情况有三种：
（1）posRes[i-1]*nums[i-1]>0,那么当前最大值就是posRes[i-1]*nums[i-1]；若小于0,那么最大负值就是posRes[i-1]*nums[i-1]
（2）nonPosRes[i-1]*nums[i-1]>0,那么当前最大值就是nonPosRes[i-1]*nums[i-1]；若大于0，那么最大正值就是nonPosRes[i-1]*nums[i-1]
（3）对posRes[i-1]*nums[i-1]==0和nonPosRes[i-1]*nums[i-1]==0单独处理，具体看代码
然后遍历整个数组即可，时间复杂度为o(n),空间复杂度也是o(n)
代码：
public class Solution {
public int maxProduct(int[] nums) {
int length=nums.length;
if(length==1)
return nums[0];
int[] posRes=new int[length+1]; //记录到当前点的正最大积
int[] nonPosRes=new int[length+1]; //记录到当前点的负最大积
int max=Integer.MIN_VALUE;
posRes[0]=1;
nonPosRes[0]=1;
for(int i=1;i<length+1;i++){
int a=posRes[i-1]*nums[i-1];
int b=nonPosRes[i-1]*nums[i-1];
if(a>0){
posRes[i]=a;
}else if(a<0)
nonPosRes[i]=a;
if(b<0)
nonPosRes[i]=b;
else if(b>0)
posRes[i]=b;
if(posRes[i]==0&&nums[i-1]>=0){
posRes[i]=nums[i-1];
}
if(nonPosRes[i]==0&&nums[i-1]<=0)
nonPosRes[i]=nums[i-1];
if(posRes[i]>max)
max=posRes[i];
}
return max;
}
}
[LeetCode] 152. Maximum Product Subarray Java
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。