Leetcode 题目解析之 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.

LeetCode第53题Maximum Subarray是求连续和最大的子数组，本题是求连续乘积最大的子数组。

在解法上是一样的，只是在求和时，是负就舍弃。但是在乘积中，因为负数*负数=正数，所以连续乘积为负数时，并不能舍弃这个数，因为如果数组的元素是负数，它可能成为乘积最大的数。

所以LeetCode第53题Maximum Subarray，只需要定义一个变量，用来记录和；本题要定义两个变量：positive和negative，分别记录当前乘积最大值和最小值。

    public int maxProduct(int[] nums) {
        int max = nums[0];
        int positive = nums[0];
        int negative = nums[0];
        for (int i = 1; i < nums.length; i++) {
            positive *= nums[i];
            negative *= nums[i];
            if (positive < negative) {
                int t = positive;
                positive = negative;
                negative = t;
            }
            positive = Math.max(positive, nums[i]);
            negative = Math.min(negative, nums[i]);
            max = Math.max(max, positive);
        }
        return max;
    }