Greedy algorithm with explanation


  • 0
    T

    //Greedy algorithm.
    Before calculating, we first find all the zeros in the given nums. Then split the given array to multiple arrays by removing those zeros.
    The absolute value of the product will increase as the length of subarray increases.
    So that the longer subarray is better than shorter subarray if the no. of negative values is even.
    For each subarray,
    If the no. of negative value is even, then just simply multiply all elements together, Otherwise, find the location of the first negative element (i) and the final negative element (j). Compare the multiple results of s[i+1, end] and s[begin, j-1].

    public int maxProduct(int[] nums) {
            int negNum = 0;
            ArrayList<Integer> zeros = new ArrayList<Integer>();
            zeros.add(-1);
            int i = 0;
            for(int num : nums){
                if(num==0)
                    zeros.add(i);
                i++;
            }
            zeros.add(nums.length);
            int product = nums[0];
            if(zeros.size() >= 3)   product = 0;
            for(i = 1; i < zeros.size(); i++){
                int a= zeros.get(i);
                int b= zeros.get(i-1);
                int[] temp = new int[a-1-b];
                for(int j = b+1; j < a; j++)
                    temp[j-b-1] = nums[j];
                product = Math.max(product, maxProductHelp(temp));
            }
            
            return product;
        }
        
        //in this function, the input array don't have have zero values;
        public int maxProductHelp(int[] nums){
            if(nums.length == 0) return Integer.MIN_VALUE;
            
            if(nums.length == 1){
                return nums[0];
            }
            int product = 1;
            for(int i : nums){
                product *= i;
            }
            int begin = -1;
            int end = nums.length;
            for(int i = 0; i < nums.length; i++){
                if(nums[i] < 0){
                    begin = i;
                    break;
                }
            }
            for(int i = nums.length-1; i>=0;i--){
                if(nums[i] < 0){
                    end = i;
                    break;
                }
            }
            int product1 = product;
            int product2 = product;
            for(int i = 0; i <= begin; i++){
                product1 /= nums[i];
            }
            for(int i = nums.length-1; i >= end; i--){
                product2 /= nums[i];
            }
            product = Math.max(product, product1);
            product = Math.max(product, product2);
            return product;
        }

Log in to reply
 

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