Java 在数组中查找 3 个数字的最大乘积
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20550037/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find maximum product of 3 numbers in an array
提问by user3011937
Given an array of integers, which can contain both +ve and -ve numbers. I've to maximize the product of any 3 elements of the array. The elements can be non-contiguous.
给定一个整数数组，它可以包含 +ve 和 -ve 数字。我必须最大化数组中任何 3 个元素的乘积。元素可以是不连续的。
Some examples:
一些例子：
int[] arr = {-5, -7, 4, 2, 1, 9}; // Max Product of 3 numbers = -5 * -7 * 9
int[] arr2 = {4, 5, -19, 3}; // Max Product of 3 numbers = 4 * 5 * 3
I've tried solving it using Dynamic Programming, but I'm not getting the expected result. It is returning the result often involving the same number twice in the multiplication. So, for the array - {4, 2, 1, 9}, it is returning - 32, which is 4 * 4 * 2.
我试过使用Dynamic Programming解决它，但我没有得到预期的结果。它返回的结果通常在乘法中两次涉及相同的数字。因此，对于数组 - {4, 2, 1, 9}，它返回 - 32，即4 * 4 * 2。
Here's my code:
这是我的代码：
public static int maxProduct(int[] arr, int count) {
return maxProduct(arr, 0, arr.length - 1, count);
}
private static int maxProduct(int[] arr, int fromIndex, int toIndex, int count) {
if (count == 1) {
return maximum(arr, fromIndex, toIndex);
} else if (toIndex - fromIndex + 1 < count) {
return 1;
} else {
return MathUtil.max(maxProduct(arr, fromIndex, toIndex - 1, count - 1) * arr[toIndex - 1],
maxProduct(arr, fromIndex, toIndex - 1, count));
}
}
MathUtil.max(int a, int b)is a method that gives maximum ofaandb.- The two values I pass to
maxmethod there are:maxProduct, when we consider last element as a part of product.maxProduct, when we don't consider it as a part of product.
countcontains the number of element we want to consider. Here3.- For
count == 1, we have to find maximum of 1 element from array. That means, we have to use maximum array element. - If
toIndex - fromIndex + 1 < count, means, there are not enough elements in the array between those indices.
MathUtil.max(int a, int b)是一种给出最大值a和的方法b。- 我传递给
max方法的两个值是：maxProduct，当我们将最后一个元素视为产品的一部分时。maxProduct，当我们不将其视为产品的一部分时。
count包含我们要考虑的元素数量。在这里3。- 对于
count == 1，我们必须从数组中找到最多 1 个元素。这意味着，我们必须使用最大数组元素。 - 如果
toIndex - fromIndex + 1 < count, 表示这些索引之间的数组中没有足够的元素。
I've an intuition that, the first ifcondition is one of the reason of failure. Because, it is only considering maximum element from an array, while the maximum product may comprise of negative numbers too. But I don't know how to take care of that.
我的直觉是，第一个if条件是失败的原因之一。因为，它只考虑数组中的最大元素，而最大乘积也可能包含负数。但我不知道如何照顾它。
The reason I'm using Dynamic Programming is that I can then generalize this solution to work for any value of count. Of course, if someone have any better approach, even for count = 3, I welcome the suggestion (I would want to avoid sorting the array, as that will be another O(nlogn)at the least).
我使用动态编程的原因是我可以将这个解决方案推广到适用于任何count. 当然，如果有人有更好的方法，即使对于count = 3，我欢迎这个建议（我想避免对数组进行排序，因为这O(nlogn)至少是另一个）。
回答by Scott Hunter
For count=3, your solution will have 1 of 3 forms:
对于 count=3，您的解决方案将具有以下 3 种形式之一：
The 3 largest positive values (assuming there ARE 3 positive values)
The largest positive value and the 2 smallest negative values (assuming there IS a positive value)
The 3 least negative values
3 个最大的正值（假设有 3 个正值）
最大的正值和 2 个最小的负值（假设存在正值）
3 个最小的负值
Each of which can be solved a lot easier than using DP.
每一个都可以比使用 DP 更容易解决。
回答by Srinath
Sort the given array in ascending order and you have to take the maximum of these cases to get the answer..
按升序对给定数组进行排序，您必须取这些情况中的最大值才能得到答案。
- product of last 3 numbers in sorted array
- Product of first two and last number in the sorted array
- 排序数组中最后 3 个数字的乘积
- 排序数组中前两个和最后一个数字的乘积
回答by openmike
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class ComputeMaxProduct {
public static void main(String[] args){
int [] arr = {4, 5, -19, 3};
List<Integer> superSet = new ArrayList<>();
for (int a : arr ){
superSet.add(a);
}
int k = 3;
int maxProduct = computeMaxProduct(superSet, k);
System.out.println("maximum product is : " + maxProduct);
}
private static int computeMaxProduct( List<Integer> superSet, int k ){
List<Set<Integer>> res = getSubsets(superSet,k);
int maxProduct = 1;
for(int index = 0; index < res.size(); index++){
int product = 1;
for(Integer i : res.get(index)){
product *= i;
}
if (product > maxProduct){
maxProduct = product;
}
}
return maxProduct;
}
private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> solution) {
//successful stop clause
if (current.size() == k) {
solution.add(new HashSet<>(current));
return;
}
//unseccessful stop clause
if (idx == superSet.size()) return;
Integer x = superSet.get(idx);
current.add(x);
//"guess" x is in the subset
getSubsets(superSet, k, idx+1, current, solution);
current.remove(x);
//"guess" x is not in the subset
getSubsets(superSet, k, idx+1, current, solution);
}
public static List<Set<Integer>> getSubsets(List<Integer> superSet, int k) {
List<Set<Integer>> res = new ArrayList<>();
getSubsets(superSet, k, 0, new HashSet<Integer>(), res);
return res;
}
}
回答by Midhula Kadiyala
public class MaxProdofThreenumbers {
public int ThreeLargeNumbers(int[] a) {
int topfirstpos = 0;
int topsecpos = 0;
int topthirdpos = 0;
int topfirstneg = 0;
int topsecneg = 0;
int prodneg = 0;
int prodpos = 0;
int prodmax = 0;
boolean flag = false;
for (int i = 0; i < a.length; i++) {
String num = a[i] + "";
if (num.contains("-")) {
String array[] = num.split("-");
num = array[1];
flag = true;
} else
flag = false;
if (flag) {
if (topfirstneg < Integer.valueOf(num)) {
topsecneg = topfirstneg;
topfirstneg = Integer.valueOf(num);
} else if (topsecneg < Integer.valueOf(num)) {
topsecneg = Integer.valueOf(num);
}
}
else {
if (topfirstpos < Integer.valueOf(num)) {
topsecpos = topfirstpos;
topfirstpos = Integer.valueOf(num);
}
else if (topsecpos < Integer.valueOf(num)) {
topthirdpos = topsecpos;
topsecpos = Integer.valueOf(num);
}
else if (topthirdpos < Integer.valueOf(num)) {
topthirdpos = Integer.valueOf(num);
}
}
}
prodneg = topfirstneg * topsecneg;
prodpos = topfirstpos * topsecpos;
if (prodneg > prodpos) {
prodmax = prodneg * topfirstpos;
} else {
prodmax = prodpos * topthirdpos;
}
return prodmax;
}
public static void main(String a[]) {
int list[] = { -29, 3, -2, -57, 8, -789, 34 };
MaxProdofThreenumbers t = new MaxProdofThreenumbers();
System.out.println(t.ThreeLargeNumbers(list));
}
}
}
回答by user4259055
This problem can be done in O(n)time.
这个问题可以O(n)及时解决。
Keep track of these 5 variables and update them during every iteration:
跟踪这 5 个变量并在每次迭代中更新它们：
- highest product of 3 numbers
- highest product of 2 numbers
- highest element
- lowest product of 2 numbers
- lowest element
- 3个数字的最高乘积
- 2个数字的最高乘积
- 最高元素
- 2个数字的最小乘积
- 最低元素
After last iteration, product of 3 numbers variable will be the answer.
最后一次迭代后，3个数字变量的乘积将是答案。
回答by Arie Milner
package interviewProblems;
import interviewProblems.exceptions.ArrayTooSmallException;
import java.util.PriorityQueue;
public class Problem5 {
public static void main(String[] args) {
int[] data1 = new int[]{}; // error
int[] data2 = new int[]{1, 5}; // error
int[] data3 = new int[]{1, 4, 2, 8, 9}; // Case: all positive --> 3-max
int[] data4 = new int[]{10, 11, 12, -20}; // Case: 1 negative --> 3-max
int[] data5 = new int[]{-5, -6, -10, 7, 8, 9}; // Case: 2+ negative --> 3-max || 1-max 2-small
int[] data6 = new int[]{-12, -10, -6, -4}; // Case: all negative --> 3-max
int[] data7 = new int[]{-10, -10, 1, 3, 2};
try {
productOfThree(data2);
} catch (Exception e) {
System.out.println(e.getMessage());
}
try {
System.out.println(productOfThree(data3));
System.out.println(productOfThree(data4));
System.out.println(productOfThree(data5));
System.out.println(productOfThree(data6));
System.out.println(productOfThree(data7));
} catch (Exception e) {
System.out.println("You should not see this line");
}
}
// O(n) time
// O(1) memory
private static int productOfThree(int[] data) throws ArrayTooSmallException {
if (data.length < 3) {
throw new ArrayTooSmallException(3 , data.length);
}
PriorityQueue<Integer> maxNumbers = new PriorityQueue<>(); // keep track of 3 largest numbers
PriorityQueue<Integer> minNumbers = new PriorityQueue<>((x, y) -> y - x); // keep track of two smallest numbers
for (int i = 0; i < data.length; i++) {
maxNumbers.add(data[i]);
minNumbers.add(data[i]);
if(maxNumbers.size() > 3) {
maxNumbers.poll();
}
if(minNumbers.size() > 2){
minNumbers.poll();
}
}
int maxLow = maxNumbers.poll();
int maxMed = maxNumbers.poll();
int maxHigh = maxNumbers.poll();
int minHigh = minNumbers.poll();
int minLow = minNumbers.poll();
int possibleProduct1 = maxHigh * maxMed * maxLow;
int possibleProduct2 = maxHigh * minHigh * minLow;
return Math.max(possibleProduct1, possibleProduct2);
}
// O(n) time
// O(n) memory
// private static int productOfThree(int[] data) throws ArrayTooSmallException {
// if(data.length < 3) {
// throw new ArrayTooSmallException("Array must be at least 3 long to preform productOfThree(int[] data)");
// }
//
// PriorityQueue<Integer> maxNumbers = new PriorityQueue<>((x , y) -> y - x); // keep track of 3 largest numbers
// PriorityQueue<Integer> minNumbers = new PriorityQueue<>(); // keep track of two smallest numbers
//
// for(int i = 0; i < data.length; i++) {
// maxNumbers.add(data[i]);
// minNumbers.add(data[i]);
// }
//
// int maxHigh = maxNumbers.poll();
// int maxMed = maxNumbers.poll();
// int maxLow = maxNumbers.poll();
//
// int minLow = minNumbers.poll();
// int minHigh = minNumbers.poll();
//
// int possibleProduct1 = maxHigh * maxMed * maxLow;
// int possibleProduct2 = maxHigh * minHigh * minLow;
//
// return Math.max(possibleProduct1 , possibleProduct2);
// }
}
https://github.com/amilner42/interviewPractice/blob/master/src/interviewProblems/Problem5.java
https://github.com/amilner42/interviewPractice/blob/master/src/interviewProblems/Problem5.java
回答by tick_tack_techie
Assuming that the a positive product is bigger than a negative product, I can think of the following way it can be done.
假设正积大于负积，我可以想到以下方法可以做到。
If there are less than two negative elements in the array, then it is simple, product of top 3(top == positive) elements.
If negative numbers are chosen, at least 2 of them have to be in the product, so that product is positive. Therefore whatever be the case, the top (positive) number will always be part of the product.
Multiply last two(negatives) and 2nd and 3rd highest(positives) and compare. Out of these two pairs whichever has higher value, will be part of the final product along with the top positive shortlisted in line above.
如果数组中的负元素少于两个，那么很简单，前 3(top == positive) 个元素的乘积。
如果选择负数，则乘积中必须至少有 2 个，因此乘积为正数。因此，无论如何，顶部（正）数将始终是产品的一部分。
将最后两个（负数）和第二和第三高（正数）相乘并进行比较。在这两对中，价值较高的将成为最终产品的一部分，并与上列入围名单中的前几名一起成为最终产品的一部分。
回答by Sumedha Khatter
It is always max of(smallest two negative digits and biggest positive or last three big positive numbers)
它总是最大的（最小的两个负数和最大的正数或最后三个大的正数）
public static void main(String args[]){
int array[] = {-5,-1,4,2,1,9};
Arrays.sort(array);
int length = array.length;
System.out.println(max(array[0]*array[1]*array[length-1],
array[length-1]*array[length-2]*array[length-3]));
}
回答by purucat
https://stackoverflow.com/users/2466168/maandoo's answer is the best.
https://stackoverflow.com/users/2466168/maandoo的答案是最好的。
As, he said, answer is max(l,r)for
正如他所说，答案是max(l,r)为了
r. product of last 3 numbers in sorted array
l. product of first two and last number in the sorted array
Let me elaborate now.
现在让我详细说明。
I think this problem is confusion because each number can be positive, negative and zero. 3 state is annoying to mange by programming, you know!
我认为这个问题很混乱，因为每个数字都可以是正数、负数和零。3 状态通过编程来管理很烦人，你知道的！
Case 1) Given three numbers
案例 1) 给定三个数字
- Use them all
- 全部使用它们
Case 2) Given four numbers
案例 2) 给定四个数字
- Positive number is show
+, Negative number is show-. - Numbers are sorted from left to right.
- 正数显示
+，负数显示-。 - 数字从左到右排序。
Case 2-1)
案例 2-1)
2-1) ---- => r (answer is negative)
2-2) ---+ => l (answer is positive)
2-3) --++ => l (answer is positive)
2-4) -+++ => r (answer is positive)
2-5) ++++ => r (answer is positive)
When a 0 is mixed in four numbers, it comes between
-and +.
当 0 与四个数字混合时，它位于-和之间
+。
Case 2-2)
Suppose smallest +was actually 0.
案例 2-2) 假设最小的+实际上是 0。
2-1) ---- => r (answer is negative)
2-2) ---0 => l (answer is 0)
2-3) --0+ => l (answer is positive)
2-4) -0++ => r (answer is 0)
2-5) 0+++ => r (answer is positive)
Case 2-3)
案例 2-3)
Suppose largest -was actually 0.
假设最大-实际上是 0。
2-1) ---0 => r (answer is 0)
2-2) --0+ => l (answer is positive)
2-3) -0++ => l (answer is 0)
2-4) 0+++ => r (answer is positive)
2-5) ++++ => r (answer is positive)
Case 2-4)
案例 2-4)
If more than two 0 is mixed, products becomes always 0 because
如果混合了两个以上的 0，则乘积始终为 0，因为
-00+
Summary for Case 2)
案例 2) 的总结
answer is consistent among Case 2-1 ~ 2-4.
Case 2-1 ~ 2-4 的答案是一致的。
2-1) r (negative or 0)
2-2) l (0 or positive)
2-3) l (0 or positive)
2-4) r (0 or positive)
2-5) r (positive)
So, we do not need to worry about 0 actually.
所以，我们实际上不需要担心 0。
Case 3) More than four numbers
情况 3) 超过四个数字
- The same with Case 2
- 与案例2相同
回答by Gautam Malhotra
u have to consider 3 cases:
1. max 3 positive elements can be the first answer(say 10*20*70).
2. max positive elements multiplied by 2 most negative answers is another candidate(say20*-40*-60).
3.in case where all array elements are negative,3 elements with minimum negative magnitude is answer(-1*-2*-3 in [-1,-2,3,-4,-5]).
for simplicity of question we can merge 1st and 3rd case.
find 3 maximum elements of array, similarly find 2 minimum elements of array.
u will get 2 candidates. Print the maximum of those candidates.
C++ Code:
#include <iostream>
#include <limits.h>
using namespace std;
int main()
{
int n; cin>>n; int arr[n]; for(int a=0;a<n;a++) cin>>arr[a];
bool flag=0;
int max1=INT_MIN,max2=INT_MIN,max3=INT_MIN;
int min1=INT_MAX,min2=INT_MAX;
for(int a=0;a<n;a++)
{
if(arr[a]>max1) {max3=max2; max2=max1; max1=arr[a];}
else if(arr[a]>max2) {max3=max2; max2=arr[a];}
else if(arr[a]>max3) max3=arr[a]; flag=1;
if(arr[a]<min1) {min2=min1; min1=arr[a];}
else if(arr[a]<min2) min2=arr[a];
}
int prod1=INT_MIN,prod2=INT_MIN;
if(max1>INT_MIN && max2>INT_MIN && max3>INT_MIN) prod1=max1*max2*max3;
if(max1>INT_MIN && min1<INT_MAX && min2<INT_MAX) prod2=max1*min1*min2;
cout<<max(prod1,prod2)<<endl;
}
