152. Maximum Product Subarray (Medium)

https://leetcode.com/problems/maximum-product-subarray/

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Solutions

class Solution {

    public int maxProduct(int[] nums) {
        int ans = 0;

        if (nums == null || nums.length == 0) {
            return ans;
        }

        // [-2]
        if (nums.length == 1) {
            return nums[0];
        }

        int min = 0;
        int max = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                // max could be 0, so choose the larger outcome
                max = Math.max(max * nums[i], nums[i]);

                // min <= 0, so min * nums[i] will be much smaller
                min = min * nums[i];
            }

            if (nums[i] == 0) {
                // start a new searching process and break up with previous consecutive sub array.
                max = 0;
                min = 0;
            }

            if (nums[i] < 0) {
                int tmp = max;
                // since nums[i]<0, you can only execute min * nums[i] to get a value >= 0 if you want to cover nums[i]
                max = min * nums[i];

                // since nums[i]<0, you can only execute previous_max * nums[i] to get a value >= 0 if you want to cover nums[i]
                min = Math.min(nums[i], tmp * nums[i]);
            }

            ans = Math.max(ans, max);
        }

        return ans;
    }
}

Incorrect Solutions

1.

class Solution {

    // Incorrect solution, fail to pass case [3, -1, 4]

    // The key idea of this solution is to keep the min when calculate the production. We need to keep
    // the min, if it's a negative value and can be a large positive if multiplied by negative value.

    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        int production = 1;
        for (int i = 0; i < nums.length; i++) {
            production *= nums[i];

            max = Math.max(max, production);
            min = Math.min(min, production);

            // If you meets zero, you need to start over the production calculation.
            if (nums[i] == 0) {
                production = 1;
            }
        }

        return max;
    }
}

2.

class Solution {

    // Incorrect solution, fail to pass case [0,2], [3, -1, 4]

    // The key idea of this solution is to keep the min when calculate the production. We need to keep
    // the min, if it's a negative value and can be a large positive if multiplied by negative value.

    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int min = nums[0];
        int max = nums[0];

        int production = nums[0];
        for (int i = 1; i < nums.length; i++) {
            production *= nums[i];

            max = Math.max(max, production);
            min = Math.min(min, production);

            // If you meets zero, you need to start over the production calculation.
            if (nums[i] == 0) {
                production = 1;
            }
        }

        return max;
    }
}

3.

class Solution {

    // Following idea is trivial and complicated.

    // This problem is not that complicated and at the first glance you may have some ideas.

    // FIXME Right blow statement is incorrect.
    // The continuous sub array must contain as many positive values as possible. Any sub arrays
    // incorporate 0 or negative values will result in a negative production.

    // The truth is that the production can be positive if the sub array doesn't contain 0 and
    // consists of even count of negative values.

    // There are two situations we will stop to check the previous scanned sub array.

    // 1. Hit 0, since 0 times everything will be 0
    // 2. Reach the end of the array.

    // Above both situation we need to sort out the impact of the negative values in the previous sub array.
    // All the negative values are expected to be processed respectively. It is recommended to use a Map to
    // keep the appeared negative values and corresponding productions.
}

References

  1. https://leetcode.com/problems/maximum-product-subarray/discuss/48473/Share-the-First-C%2B%2B-Solution-with-Notes
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""