2ms JAVA O(1) space O(n) time solution


  • 0

    Thinking procedure:
    If an array contains all positive numbers, then the subarray would be itself.

    For arrays which have negative numbers:
    For example, array a = [-1,2,3,4,-2,3,2,-1,3,-2,3,2,-1], there are five negative numbers in this array.

    Those negative numbers' positions are 0,4,7,9,12

    Suppose p(x,y) is the product of a[x]*...*a[y], we need to compare following products of subarrays(all have positive results):
    p(0,4)
    p(0,11) = P(0,4)*p(4,7)*p(7,11) /(a[4]*a[7])
    p(1,7)
    p(1,12) = p(1,7)*p(7,9)*p(9,12) /(a[7]*a[9])
    P(7,11)
    p(9,12)

    Since all the numbers are integer, p(0,11) >= {p(0,4), p(4,7), p(7,11)}, p(1,12) >= {p(1,7),p(7,9),p(9,12)}. The question now becomes comparing the two largest contiguous subarrays. So we just need to calculate p(0,11) and p(1,12).

    We know that p(1,12) = p(0,12)/a[0]. In order to get p(1,12), we just need two variables to store the maximum negative product and minimum negative product separately.

    For arrays which contain 0, each 0 will split the arrays apart. We calculate each part to get the result.

        public int maxProduct(int[] nums) {
            int len = nums.length;
            if(len == 1) return nums[0];
            int res = 0;
            int maxP = 0, maxN = Integer.MIN_VALUE, minN = 0;
            int tmp = 1, curMax = 0;
            for(int i = 0; i < len; i++){
                if(nums[i] == 0){
                    int cur = minN/maxN;
                	curMax = maxP>cur? maxP:cur;
                	if(curMax > res) res = curMax;
                	tmp = 1;
                	maxP = 0;
                	maxN = Integer.MIN_VALUE;
                	minN = 0;
                	continue;
                }
                tmp *= nums[i];
                if(tmp > maxP){
                    maxP = tmp;
                }
                if(tmp<0 && maxN == Integer.MIN_VALUE){
                    maxN = tmp;
                }
                else if(tmp < minN){
                    minN = tmp;
                }
            }
            int cur = minN/maxN;
            curMax = maxP>cur? maxP:cur;
            if(curMax > res)res = curMax;
            return res;   
        }
    

  • 0
    Y

    What if there are float numbers? I know there aren't float numbers in test cases but this method is not generic


  • 0

    @yunwwww The input provided by this problem are int[], not float[]. If there are float numbers, then things become complicated.


Log in to reply
 

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