找到两两乘积的最大和

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;
}

问题描述

（图片显示了一个网站登录界面，要求输入用户名和密码）

- user7500403

---

你能提供问题的链接吗？ - Mitch

你能否尝试添加以下条件： if (a == null || b == null) return 0; 并告诉我们结果是否有所改变？ 也许这是一些边缘情况，导致你的代码运行时出现了NullPointerException？ - Yaron Grushka

嗯，看起来不错，可能是溢出问题吗？你可以尝试使用https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html。 - Mitch

@YaronGrushka，描述中写道“1 <= n <= 10^3”，所以我认为不是这个。 - Mitch

@MitchelPaulin 确实，但值得一试。像 LeetCode 这样的地方喜欢那些边角情况。他的方法看起来应该是有效的。 - Yaron Grushka

Answer 1

我想我知道问题所在，但没有访问权限，无法确定。考虑这种情况：a [i] = 10 ^ 5 和 b [i] = 10 ^ 5，是问题中允许的最大值，现在 a [i] * b [i] = 10 ^ 10。由于a和b是整数类型，中间结果存储为整数。您将遇到溢出，因为数字10^10超出了int的限制。

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

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

- Mitch