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

Question

给定一个整数数组,它可以包含+ 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,意味着,那些索引之间的数组中没有足够的元素.

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

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

Answer 1

按升序对给定数组进行排序,您必须采用这些情况的最大值才能得到答案.

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

Answer 2

对于count = 3,您的解决方案将包含3种形式中的1种:

1. 3个最大正值(假设有3个正值)

2. 最大的正值和2个最小的负值(假设有一个正值)

3. 3个最小的负值

与使用DP相比,每种方法都可以轻松解决.

Answer 3

它始终是最大值（最小的两个负数和最大的正数或最后三个大正数）

public static void main(String args[]){

    int array[] = {-5,-1,4,2,1,9};
    Arrays.sort(array);

    int length = array.length;
    System.out.println(max(array[0]*array[1]*array[length-1], 
                           array[length-1]*array[length-2]*array[length-3]));   
}