[LeetCode] 152. 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]，很显然应该返回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;
        }
}