转载

java – 在数组中查找3个数字的最大乘积

给定一个整数数组,它可以包含ve和-ve数.我要最大化数组中任何3个元素的乘积.元素可以是非连续的.

一些例子：

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

我尝试使用动态编程解决它,但我没有得到预期的结果.它在乘法中返回通常涉及相同数字两次的结果.因此,对于数组 – {4,2,1,9},它返回 – 32,即4 * 4 * 2.

这是我的代码：

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)是一个给出a和b的最大值的方法.

>我传递给max方法的两个值有：

> maxProduct,当我们将最后一个元素视为产品的一部分时.

> maxProduct,当我们不将其视为产品的一部分时.

> count包含我们要考虑的元素数量.这里3.

>对于count == 1,我们必须从数组中找到最多1个元素.这意味着,我们必须使用最大数组元素.

>如果toIndex – fromIndex 1<count,表示这些索引之间的数组中没有足够的元素.

我有一种直觉,即第一种条件是失败的原因之一.因为,它只考虑来自阵列的最大元素,而最大乘积也可以包括负数.但我不知道该如何处理.

我使用动态编程的原因是我可以将此解决方案概括为适用于任何计数值.当然,如果有人有更好的方法,即使对于count = 3,我也欢迎这个建议(我希望避免对数组进行排序,因为这至少会是另一个O(nlogn)).

原文 https://codeday.me/bug/20190113/521488.html

正文到此结束