题目：

 

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
     
      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;    }}