Share my non-DP accepted code


  • 1
    B
    public class Solution {
        public int maxProduct(int[] A) {
            //adjust input parameter
            return maxSubarray(A, 0, A.length-1);
        }
        
        private int maxSubarray(int[] A, int x, int y) {
            int max = 1;
            
            //Array length is 1
            if (y-x+1 == 1) return A[x];
            
            //Multiply all the numbers
            for (int i = x; i <= y; i++) {
                max *= A[i];
            }
            
            if (max > 0) {
                //Even number of negative number
                return max;
            } else if (max == 0) {
                //Array contains 0, therefore process the array piece by piece
                max = 0;
                int start = x;
                while (start <= y) {
                    if (A[start] != 0) {
                        int i = start;
                        while (i <= y && A[i] != 0) {
                            i++;
                        }
                        //recursive call on each piece
                        max = Math.max(max, maxSubarray(A, start, i-1));
                        start = i;
                    }
                    start++;
                }
            } else {
                //Array contains no 0 and odd number of negative numbers.
                int max1 = 1, max2 = 1;
        
                //ignore the left most negative number
                for (int m = x; m <= y; m++) {
                    if (A[m] < 0) {
                        for (int i = m+1; i <= y; i++) {
                            max1 *= A[i];
                        }
                        break;
                    }
                }
                
                //ingnore the right most negative number
                for (int m = y; m >= x; m--) {
                    if (A[m] < 0) {
                        for (int i = m-1; i >= x; i--) {
                            max2 *= A[i];
                        }
                        break;
                    }
                }
                max = max1 > max2 ? max1 : max2;
            }
            return max;    
        }
    }

  • 4
    Y
    public class Solution {
    public int maxProduct(int[] A) {
        if (A == null || A.length == 0){
            return 0;
        }
        int count = 1;
        int prefix = 1;
        int maxV = A[0];
        for (int i=0; i<A.length; i++){
            count = count * A[i];
            maxV = Math.max(count, maxV);
            if (count == 0){
                count = 1;
                prefix = 1;
            }
            else if (count < 0 && prefix >0){
                prefix = count;
            }
            else {
                maxV = Math.max(maxV, count/prefix);
            }
        }
        return maxV;
    }
    

    }


Log in to reply
 

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