在数组中查找3个数字的最大乘积 [英] Find maximum product of 3 numbers in an array

问题描述

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

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.

一些例子：

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 。

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.

这是我的代码：

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 方法的两个值有：
  
  $ b当我们将最后一个元素视为产品的一部分时，$ b
  • maxProduct 。
  
  
  • maxProduct ，当我们不将其视为产品的一部分时。
  
  
  • MathUtil.max(int a, int b) is a method that gives maximum of a and b.
  • The two values I pass to max method 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.

    我有一个直觉，第一个 if 条件是失败的原因之一。因为，它只考虑来自阵列的最大元素，而最大乘积也可以包括负数。但是我不知道如何解决这个问题。

    I've an intuition that, the first if condition 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.

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

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

    推荐答案

    对给定数组进行排序升序，你必须取这些案件的最大值
    才能得到答案..

    Sort the given array in ascending order and you have to take the maximum of these cases to get the answer..

    
    
    1. 最后3个数字的产品排序数组
    
    
    2. 排序数组中前两个和最后一个数字的乘积
    
    

    这篇关于在数组中查找3个数字的最大乘积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！