首页 > 代码库 > Maximum Product Subarray Leetcode

Maximum Product Subarray Leetcode

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.

这道题和Maximum Sum Subarray类似,也是考虑什么时候可以取得最大值。sum的话一遇到负数就可以重新考虑,product的话负数*负数可能是最大值,所以要保留局部最大值和局部最小值。

每次考虑最大值的时候,在:

前面的最大值乘这个数本身(这个数是正数),

这个数本身(这个数是负数或者这个数前面的数是负数,这个数本身是正数),

最小值乘这个数(最小值和这个数都是负数),

这三个里面选局部最大值。

每次考虑最小值的时候,在:

前面的最小值乘这个数本身(这个数是正数),

这个书本身(这个数是负数,前面的最小值也是负数),

最大值乘这个数(最大值是正数,这个数是负数),

这三个里面选局部最小值。

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] curMax = new int[nums.length];
        int[] curMin = new int[nums.length];
        int res = nums[0];
        curMax[0] = nums[0];
        curMin[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curMax[i] = Math.max(Math.max(curMax[i - 1] * nums[i], nums[i]), curMin[i - 1] * nums[i]);
            curMin[i] = Math.min(Math.min(curMax[i - 1] * nums[i], nums[i]), curMin[i - 1] * nums[i]);
            if (curMax[i] > res) {
                res = curMax[i];
            }
        }
        return res;
    }
}

改良了一下,可以用O(1) space,但是思路是一样的

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = nums[0];
        int curMax = nums[0];
        int curMin = nums[0];
        int max, min;
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(Math.max(curMax * nums[i], nums[i]), curMin * nums[i]);
            min = Math.min(Math.min(curMax * nums[i], nums[i]), curMin * nums[i]);
            if (max > res) {
                res = max;
            }
            curMax = max;
            curMin = min;
        }
        return res;
    }
}

 这个动态规划做的不顺利,以后回顾一下吧。

Maximum Product Subarray Leetcode