寻找成对乘积的最大和

Question

我正在解决Java中的一个问题，其中我必须找到2个整数数组的最大成对乘积。

示例：

array 1 -> [1, 3, -5]
array 2 -> [-2, 4, 1]

output: 23            // (3 * 4) + (1 * 1) + (-5 * -2)

我的当前代码也产生此输出。

我的解决方案

对两个数组进行排序，然后将两个数组中相同索引处的数字相乘，然后将每对的乘积相加。

问题

我的解决方案是使用我不知道的测试用例进行测试的。我的解决方案无法通过所有测试用例。我不确定是否有任何输入会使我的解决方案失败。

问题

给定问题的解决方案是否出了问题，导致我的代码无法通过所有测试用例？

代码

private static long maxSum(int[] a, int[] b) {
    long result = 0;

    Arrays.sort(a);
    Arrays.sort(b);

    for (int i = a.length - 1; i >= 0; i--) {
        result += a[i] * b[i];
    }

    return result;
}

问题描述

Answer 1

我想我可能知道问题出在哪里。考虑a[i] = 10^5和b[i] = 10^5a[i] * b[i]= 10 ^ 10的情况。由于a和b是整数类型，因此中间结果以整数形式存储，因此会溢出，因为10 ^ 10的数字超出int的限制。

要解决此问题，您可以将数组值强制转换为long。

result += Long.valueOf(a[i]) * Long.valueOf(b[i]);