Maximum Product Subarray 191

Question

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

Solution

prod[i]记录了以第i个元素结尾的最大和最小product。

状态函数：

prod[i].max=max(max(prod[i-1].max*nums[i], prod[i-1].min*nums[i]),nums[i])
prod[i].min=min(min(prod[i-1].max*nums[i], prod[i-1].min*nums[i]),nums[i])

因为不确定当前元素的正负，所以要和之前的max和min都相乘，较大者和当前元素比较求max，较小者和当前元素比较求min。

也可以分情况讨论当前元素的正负，以确定求max和min的时候是和之前的max相乘还是和min相乘。

代码如下：

class Pair{
    int max;
    int min;
    public Pair(int max, int min){
        this.max = max;
        this.min = min;
    }
}

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: an integer
     */
    public int maxProduct(int[] nums) {
        // write your code here
        if(nums == null || nums.length == 0){
            return 0;
        }

        Pair[] prod = new Pair[nums.length];
        prod[0] = new Pair(nums[0], nums[0]);

        int maxProd = prod[0].max;
        for(int i = 1; i < nums.length; i++){
            int max = Math.max(Math.max(prod[i - 1].max * nums[i], prod[i - 1].min * nums[i]), nums[i]);
            int min = Math.min(Math.min(prod[i - 1].max * nums[i], prod[i - 1].min * nums[i]), nums[i]);
            prod[i] = new Pair(max, min);
            maxProd = Math.max(maxProd, prod[i].max);
        }

        return maxProd;
    }
}

分情况讨论version

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: an integer
     */
    public int maxProduct(int[] nums) {
        int[] max = new int[nums.length];
        int[] min = new int[nums.length];

        min[0] = max[0] = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            min[i] = max[i] = nums[i];
            if (nums[i] > 0) {
                max[i] = Math.max(max[i], max[i - 1] * nums[i]);
                min[i] = Math.min(min[i], min[i - 1] * nums[i]);
            } else if (nums[i] < 0) {
                max[i] = Math.max(max[i], min[i - 1] * nums[i]);
                min[i] = Math.min(min[i], max[i - 1] * nums[i]);
            }

            result = Math.max(result, max[i]);
        }

        return result;
    }
}