【原题】 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],很显然应该返回6(即2 x 3)。若给定数组为[2,3,-2,4,-1],则应该返回48(即数组中所有数想乘)。想象什么情况才可能为最大值,一个是连续正数相乘的情形,还有一种就是负负得正的情形。
第二种情况下,能得到正的最大值只可能是之前负的最大值再乘上一个负数。所以我们不仅要保留当前正数最大值,而且还要保留目前为止的最小值(以防负负得正的情况出现,这里也是看了解析才明白,刚开始还使用记录负数个数的方法试图解决负负得正的问题,看了解析之后才发现自己的代码又长又臭【捂脸】)
public class Solution {
public int maxProduct(int[] nums) {
if(nums.length==0) return 0;
int max=nums[0], min=nums[0];
int ans=max;
for(int i=1;i<nums.length;i++){
int tmpMin=min;
min=Math.min(nums[i], Math.min(min*nums[i],max*nums[i]));
max=Math.max(nums[i], Math.max(tmpMin*nums[i], max*nums[i]));
ans=Math.max(ans, max);//每次保留目前为止的最大值,直接使用max的话,若后面为一个负数,则前面的最大值就会被清洗
}
return ans;
}
}