java - 在Java中查找负数的最大乘积

Question

我正在学习 Java 的半高级类(class)。我自学 JavaScript 是一种爱好，所以我不是一个真正的初学者，但在制作算法方面我不是很有经验。我们有一道作业题要做。它遵循以下原则:给定 n 个正整数，其中 n >= 5 通过选择两个(不一定连续的)数字作为因子找到可能的最大乘积。 p>

例如，如果输入是:3 6 0 10 4，输出应该是60。

这看起来相当简单。我只是选择了最大的两个并将它们相乘:

System.out.println("How many numbers will you give me?");
int n = sc.nextInt();
if (n < 5) throw new Error("n must be at least 5");
System.out.println("Enter the numbers");
int max1 = 0, max2 = 0;
for (int i = 0; i < n; ++i) {
    int newInt = sc.nextInt();
    if (newInt > max1) {
        max2 = max1;
        max1 = newInt;
    } else if (newInt > max2) {
        max2 = newInt;
    }
}
System.out.println("The largest product is " + (max1 * max2));

这非常有效。现在，在这个(可选)之后有一个“奖励”或扩展问题。我决定试一试。问题是类似的:给定 n(不一定是正数)整数，通过选择两个(不一定是连续的)数字作为因子来找到可能的最大乘积。鉴于 5 <= n <= 25

，该程序应该会在合理的时间内运行

旧程序的问题在于，它会因 -6 -5 3 0 4 这样的输入而失败。当正确答案是 30 时，它会输出 12。我决定检查绝对值而不是实际值，因此将包含负数。该代码是这样的:

System.out.println("How many numbers will you give me?");
int n = sc.nextInt();
if (n < 5) throw new Error("n must be at least 5");
System.out.println("Enter the numbers");
int max1 = 0, max2 = 0;
for (int i = 0; i < n; ++i) {
    int newInt = sc.nextInt(), absValue = Math.abs(newInt);
    if (absValue > Math.abs(max1)) {
        max2 = max1;
        max1 = newInt;
    } else if (absValue > Math.abs(max2)) {
        max2 = newInt;
    }
}
System.out.println("The largest product is " + (max1 * max2));

这适用于 -6 -5 3 0 4，正确给出 30 但 -6 -3 1 5 4 失败。它给出了 -30 的答案，这显然是不正确的。

我尝试了一种蛮力解决方案(检查所有可能的产品)，它对 n = 5 非常有效，但需要 n! 迭代，这意味着它需要n = 25 的时间很长。我对如何解决这个问题感到困惑。先感谢您。

Answer 1

问题是检查绝对值会丢弃它们可能为负的信息。您需要两个正数或两个负数。

实现这一点的最简单方法是扫描，找到两个最小的和两个最大的数字。

乘以最小的两个。将两个最大的相乘。哪个更大就是你的结果。