在数组中查找 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}324 * 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)是一种给出 maximum of and 的方法。ab
• 我传递给方法的两个值是：max
  • maxProduct，当我们将最后一个元素视为产品的一部分时。
  • maxProduct，当我们不认为它是产品的一部分时。
• count包含我们要考虑的元素数。这里。3
• 对于 ，我们必须从数组中找到最多 1 个元素。这意味着，我们必须使用最大数组元素。count == 1
• 如果 ，则表示这些索引之间的数组中没有足够的元素。toIndex - fromIndex + 1 < count

我有一个直觉，第一个条件是失败的原因之一。因为，它只考虑数组中的最大元素，而最大乘积也可能由负数组成。但我不知道如何处理这个问题。if

我使用动态规划的原因是，我可以推广此解决方案以适用于 的任何值。当然，如果有人有任何更好的方法，即使是，我也欢迎这个建议（我想避免对数组进行排序，因为这至少是另一个）。countcount = 3O(nlogn)