在数组中查找 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 方法的两个值是:
  • 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 的值.当然，如果有人有更好的方法，即使对于 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屋！