计算机考研408编程题-2025年-41题

题目

解析

最直观的方法是使用两层嵌套循环，但这会导致 $O(n^2)$ 的时间复杂度。为了达到最高效，可以采用动态规划/贪心的思想，通过从后往前遍历数组，在 $O(n)$ 的时间复杂度内解决问题。

（1）算法的基本设计思想

要计算 A[i] 与 A[j] (其中 $0 \le i \le j \le n-1$) 乘积的最大值，我们需要考虑 A[i] 的正负性：

1. 如果 A[i] 为正数：为了使乘积最大，需要找到它之后（包含自身）最大的数相乘。
2. 如果 A[i] 为负数：为了使乘积最大，需要找到它之后（包含自身）最小的数（即绝对值最大的负数）相乘。
3. 如果 A[i] 为 0：无论乘什么数，结果都为 0。

因此，对于每一个位置 i，实际上只需要知道子数组 A[i...n-1] 中的最大值和最小值。

为了在时间上尽可能高效，我们可以从后往前（逆序）遍历数组 A。 在遍历的过程中，我们维护两个变量：max_val（记录当前遇到的最大值）和 min_val（记录当前遇到的最小值）。 对于当前元素 A[i]，先用它更新 max_val 和 min_val，然后计算 A[i] * max_val 和 A[i] * min_val，这两个乘积中的较大者，就是 res[i] 的值。 这种方法只需要遍历数组一次，避免了重复计算。

（2）使用 C++ 语言实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <algorithm>

void calMulMax(int A[], int res[], int n) {
	if (n <= 0) return;

	// 初始化后缀最大值和后缀最小值，初始均设为数组最后一个元素
	int max_val = A[n - 1];
	int min_val = A[n - 1];

    // 逆序遍历数组 
    for (int i = n - 1; i >= 0; i--) {
    	// 更新最大值和最小值
    	max_val = std::max(max_val, A[i]);
        min_val = std::min(min_val, A[i]);

        // 计算当前元素的最大值与最小值的乘积，取两者中的最大值存入 res[i]
	    res[i] = std::max(A[i] * max_val, A[i] * min_val); 
	}
}

（3）时间复杂度和空间复杂度

• 时间复杂度：$O(n)$ 算法中只包含一个 for 循环，将长度为 $n$ 的数组逆序遍历了一次。循环体内部执行的都是常数时间 $O(1)$ 的基本操作（比较、乘法、赋值）。因此，总的时间复杂度为线性阶 $O(n)$，这是此问题时间复杂度的最优解。
• 空间复杂度：$O(1)$ 算法在执行过程中，除了输入参数 A、res 和 n 之外，仅声明了几个额外的整型局部变量（max_val, min_val, i）。这些变量占用的内存空间不随输入数据规模 $n$ 的增大而增大。由于结果数组 res 是题目要求输出的一部分，通常不计入辅助空间，因此该算法的辅助空间复杂度为 $O(1)$。