Leetcode 152) Maximum Product Subarray

28 May 2021 in Algorithms

• valid 변수를 나중에 추가해서 결국에는 맞았는데.. 이렇게 푸는게 의미가 있을까?

class Solution {
    public int maxProduct(int[] nums) {
        int start=0;
        int neg_first=0;
        int neg_last=0;
        boolean n=false;
        int prd=1;
        boolean valid = false;
        int max=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            start=i;
            n=false;
            prd=1;
            valid=false;

            while(nums[i] !=0){
                if(nums[i]<0){
                    if(!n){
                        n=true;
                        neg_first = i;
                        neg_last = i;
                    }else{
                        neg_last=i;
                    }
                }

                prd*=nums[i];
                valid=true;
                i++;
                if(i==nums.length){
                    break;
                }
            }

            if(i !=nums.length){
                if(nums[i]==0){
                    max= Math.max(0,max);
                }
            }
            if(prd>=0){
                if(max<=prd && valid){
                    //System.out.println(prd);
                    max=prd;
                }
            }else{
                if(i-start<=1){

                    max= Math.max(max,prd);
                    continue;

                }
                //현재꺼에서 마지막 neg를 pop해주는 것.
                int tmp1 = prd;
                while(neg_last<i){
                    System.out.println(prd);
                    tmp1/=nums[neg_last];
                    neg_last++;
                }
                //start에서 처음 neg까지를 pop해주는 것. 
                System.out.println(tmp1);

                int tmp2 =prd;
                while(start<=neg_first){
                    tmp2/=nums[neg_first];
                    neg_first--;
                }

                max= Math.max(max,tmp1);
                max= Math.max(max,tmp2);
            }
        }
        return max;

    }
}

다른 답안

class Solution {
    public int maxProduct(int[] nums) {
        /*
            there are three scenario's in this problem

            * in case of all positive nums, we just have to multiply all values from left to right

            * in case of a 0 we have to reset the product and start fresh

            * in case of a negative num, it depends on whether it is even or odd
              if even we may have a larger number, if odd it will make even a larger number small.
              for example - [4, -2, 1, 8]
              in this case if we only multiply from left to right we will end up with 4
              but the ans is 8. So this means we need to multiply from right to left as well 
              to find the max product
        */
        
        int product = 1;
        int max = Integer.MIN_VALUE;
        
        for (int i = 0; i < nums.length; i++) {
            product = product * nums[i];
            max = Math.max(product, max);
            if (product == 0) product = 1;
        }
        
        product = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            product = product * nums[i];
            max = Math.max(product, max);
            if (product == 0) product = 1;
        }
        
        
        return max;
    }
}

while(i<nums.length && nums[i] !=0){
    ;
} 
대신에 이렇게 사용?;
while(nums[i] !=0){

    if(i==nums.length){
        break;
    }
}