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

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » java – 在数组中查找3个数字的最大乘积

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址