The solution can't pass this case [-200000000, 1, 200000000]!!! DP is not the right solution.


  • 0
    K

    [alt text](0_1472948320692_Screen Shot 2016-09-03 at 5.17.53 PM.png image url)

    We should be very careful when we multiply numbers as the result could overflow. For example, 200000000 * -200000000 overflows but either of them doesn't. The following is my solution. The key point is to avoid multiplying any numbers if we know they are not going to be the answer.

    1. split the whole array into different parts which don't have 0.
      [-2,-1,0,4,0,3,-2,1,-1,-3,2] -> [-2, -1], [4], [3,-2,1,-1,-3,2]
    2. find the max production of each part
      a) if there are even number of negatives, return product of the whole part, e.g. [-2, -1] -> -2 * -1 = 2;
      b) if there are odd number of negatives, find the first and the last negatives and return max(product(nums, start, last_negative - 1), prod(nums, first_negative + 1, end)), e.g. [3,-2,1,-1,-3,2] -> max(3 * -2 * 1 * -1, 1 * -1 * -3 * 2)
    3. return the max found in step 2).

    ***I know the following code is very long. So TL;;DR;;

    class Solution {
    public:
        int prod(vector<int>& nums, int start, int end) {
            int prod = nums[start];
            for (int i = start + 1; i <= end; i++) {
                prod *= nums[i];
            }
            return prod;
        }
        int max_element(vector<int>& nums, int start, int end) {
            int max_element = nums[start];
            for (int i = start + 1; i <= end; i++) {
                max_element = max(max_element, nums[i]);
            }
            return max_element;
        }
        int maxProduct(vector<int>& nums, int start, int end) {
            if (start == end) {
                return nums[start];
            }
            int num_negatives = 0;
            for (int i = start; i <= end; i++) {
                if (nums[i] < 0) {
                    num_negatives++;
                }
            }
            if (num_negatives % 2 == 0) {
                return prod(nums, start, end);
            } else {
                int first_negative = -1, last_negative = -1;
                int index = start;
                while (index <= end && nums[index] > 0) {
                    index++;
                }
                if (index != end + 1) {
                    first_negative = index;
                }
                index = end;
                while (index >= start && nums[index] > 0) {
                    index--;
                }
                if (index != start - 1) {
                    last_negative = index;
                }
                if (start > last_negative - 1) {
                    return prod(nums, first_negative + 1, end);
                } else if (first_negative + 1 > end) {
                    return prod(nums, start, last_negative - 1);
                } else {
                    return max(prod(nums, start, last_negative - 1), prod(nums, first_negative + 1, end));
                }
            }
        }
        int maxProduct(vector<int>& nums) {
            int max_product = nums[0];
            vector<int> zero_index;
            for (int i = 0; i < nums.size(); i++) {
                max_product = max(nums[i], max_product);
                if (nums[i] == 0) {
                    zero_index.push_back(i);
                }
            }
            zero_index.push_back(nums.size());
            
            int start = 0;
            for (int index : zero_index) {
                int end = index - 1;
                while (end >= 0 && nums[end] == 0) {
                    end--;
                }
                if (start <= end) {
                    max_product = max(max_product, maxProduct(nums, start, end));
                }
                start = index + 1;
            }
            return max_product;
        }
    };
    

  • 0

    It overflows, but the dp method is right. They just don't want you waste time handling overflow.


  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.