Java solution beats 98.61%


  • 2
    L
    public class Solution {
        public int maxProduct(int[] nums) {
            int product, i;
            int ans = Integer.MIN_VALUE;
            for (i = 0, product = 1; i < nums.length; i++) {
                product = nums[i] == 0? 1 : (product * nums[i]);
                ans = Integer.max(ans, nums[i] == 0? 0 : product);
            }
            for (i = nums.length - 1, product = 1; i >= 0; i--) {
                product = nums[i] == 0? 1 : (product * nums[i]);
                ans = Integer.max(ans, nums[i] == 0? 0 : product);
            }
            return ans;
        }
    }
    

    For an array without any "0", there are 2 situations.

    Situation 1. (the count of negative numbers) % 2 == 0
    The answer is the product of all numbers. (Because all minus can cancel each other out.)

    Situation 2. (the count of negative numbers) % 2 == 1
    Just pick out one negative number, calculate separately the left-hand and right-hand side subarray (the situation will come to situation 1, and the product of situation 1 must be a non-negative number) of that number, and then find a bigger number to update the answer.
    For which negative number to pick, we can do it by enumeration.
    The order of each calculation does not matter, so Prefix Product can be used. In the code, during the first For Loop, we calculate all left-hand side subarrays. And we calculate right-hand side subarrays in the second For Loop.


    If there are any "0" members, imaging separating the array into many subarrays, and just consider "0" is a signal representing the beginning of a subarray.



Log in to reply
 

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