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.
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
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
