Largest Product of Subset Array - Coding in a Smart Way

Largest Product of Subset Array - Coding in a Smart Way
Given an array of integer numbers A, and an positive integer N, find the largest product of subset array A with N elements in that array. For example, if A = [1, -3, 2, -5], and N = 3, return 30 for -3.2.-5.

The problem seems easy but actually quite difficult to handle all of the cases correctly:

– Can we obtain positive product? If possible, select the largest-absolute numbers

– If we can only obtain negative product, select the smallest-absolute numbers

– What happen if the array contains zero elements.

To solve the problem correctly, I list all cases possible below:

– A contains exactly N elements

– There are less than N numbers of non-zero elements -> return 0

– No positive number: N odd or even

– No negative number: take all largest positive numbers

– Other case: take N largest-absolute numbers. If the product is positive, return it. Otherwise, switch one positive/negative in the product with one negative/positive corresponding. For example A = [10, -5, -4, 2], N = 3, return 10.-5.-4. If A = [10, -5, 4, 3, -2], 10.-5.4 < 0, either switch -5 with 3 or 4 with -2. In this case, we take 10.4.3 = 120 instead of 10.-5.-2=100.

public static int compute(List<Integer> A, int N){
    List<Integer> positives = new ArrayList<Integer>();
    List<Integer> zeros = new ArrayList<Integer>();
    List<Integer> negatives = new ArrayList<Integer>();
    for (int number : A){
        if (number > 0){
            positives.add(number);
        } else if(number == 0){
            zeros.add(number);
        }else{
            negatives.add(number);
        }
    }
    //sort
    Collections.sort(positives);
    Collections.sort(negatives);
   
    int numnNonZero = positives.size() + negatives.size();
    if (A.size() == N){
        return productFirst(A, A.size());
    } else if (numnNonZero < N){ return 0; }
      //have enough N non-zero elements to select
      if (negatives.size() == 0){
        return productLast(positives, N);
      }
      else if (positives.size() == 0){
        if (N % 2 == 0){
          return productFirst(negatives, N);
        } else{
          if (zeros.size() > 0){
                return 0;
          } else{
                return productLast(negatives, N);
          }
        }
    }
   
    //
    int result = 1;
    int runPositive = positives.size() - 1;
    int runNegative = negatives.size() - 1;
    for (int i = 0; i < N ;i++){
      if (runPositive == 0){
        result *= negatives.get(runNegative); runNegative--;
      } else if (runNegative == 0)
      {
        result *= positives.get(runPositive); runPositive--;
      }else{
        if (Math.abs(runPositive) > Math.abs(runNegative)){
          result *= positives.get(runPositive);
          runPositive--;
        }else{
          result *= negatives.get(runNegative);
          runNegative--;
        }
      }
    }
   
    if (result > 0){
        return result;
    }else{
        if (runPositive == positives.size() - 1){
            //no positive is added, replace last added negative with the positive
            return result / negatives.get(runNegative + 1) * positives.get(runPositive);
        } else if (runNegative == negatives.size() - 1){ // how is this possible?
            //no negative is added, replace last positive with the negative
            return result / positives.get(runPositive + 1) * negatives.get(runNegative);
        } else{
            //return max of above 2 cases
            return Math.max(result / positives.get(runPositive + 1) * negatives.get(runNegative),
                    result / negatives.get(runNegative + 1) * positives.get(runPositive));
        }
    }
}

private static int productFirst(List<Integer> A, int N){
    int result = 1;
    for (int i = 0; i < N; i++){
        result *= A.get(i);
    }
    return result;
}

private static int productLast(List<Integer> A, int N){
    int result = 1;
    for (int i = 1; i <= N; i++){
        result *= A.get(A.size() - i);
    }
    return result;
}

Read full article from Largest Product of Subset Array - Coding in a Smart Way