从数组中的三个整数中找出你能得到的最高乘积——如何使用蛮力求解

Question

int arr[] = {10, 10, 1, 3};

假设：假设每个int都是正的。假设数组至少包含3个整数

从上述数组中的三个整数中找出最高乘积。我们应该退还300英镑（10英镑）∗ 10∗ 3).

我想用蛮力法解决这个问题。基本上，我想把每个整数乘以另一个整数，然后把乘积乘以另一个整数。有谁能告诉我如何使用嵌套的3个循环来实现这一点，因为在尝试优化方法之前，我想先了解如何使用蛮力来实现这一点。

谢谢。

Answer 1

有一些方法可以忽略暴力。

1.分类

首先可以对数组进行排序，这需要O（nlogn）时间。排序后，选择最后3项。因为它们是最高的物品，所以产品将是最高的

注意：如果数组中有任何负数，它将不起作用。为了修复它，你可以检查一些组合。首先计算前3项产品，然后计算最后3项，然后计算前2项和最后1项。其中之一将是最伟大的。

2.动态规划

请参阅矩阵链乘法或最大增长长度问题和动态规划解决方案。它将帮助你理解什么是动态规划，并创建简单的算法来解决你的问题。

Answer 2

使用三个for循环：

public static Integer highestProduct(int array[]) 
{
    if((array==null)||(array.length<3))
    {
        return null;
    }

    else
    {
        int max_product = Integer.MIN_VALUE;
        for(int i=0;i<array.length;i++)
        {
            for(int j=i+1;j<array.length;j++)
            {
                for(int k=j+1;k<array.length;k++)
                {
                    int product = array[i]*array[j]*array[k];
                    if(product>=max_product)
                    {
                        max_product = product;
                    }
                }
            }
        }
        return max_product;
     }
 }