第1题
（本题 13 分）设有两个长度均为 n 的一维整型数组 A 和 res，对数组 A 中的每个元素 A [i]，计算 A [i] 与 A [j]（0≤i≤j≤n-1）乘积的最大值，并将其保存到 res [i] 中。例如，若 A [ ]={1,4,-9,6}，则得到 res [ ]={6,24,81,36}。现给定数组 A，请设计一个时间和空间上尽可能高效的算法 calMulMax，求 res 中各元素的值。函数原型为：void calMulMax (int A [ ],int res [ ],int n)。要求如下：
（1）给出算法的基本设计思想。（4 分）
（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。（7 分）
（3）说明你所设计算法的时间复杂度和空间复杂度。（2 分）
参考答案：
（1）算法的基本设计思想：从后向前扫描一趟数组 A，对每个 A [i]（0≤i≤n-1），分别找到从 A [n-1] 到 A [i] 中的最大值 Max 和最小值 Min，然后分情况处理：①若 A [i]≥0，则 A [i] 与 Max 相乘；②若 A [i]<0，则 A [i] 与 Min 相乘；相乘的结果保存在 res [i] 中。
（2）算法实现：
void calMulMax(int A[], int res[], int n)
{
int i, Max, Min;
Max = Min = A[n - 1]; // 初始化最大值和最小值为数组最后一个元素
for (i = n - 1; i >= 0; i--) // 从后向前扫描数组A
{
if (A[i] > Max) Max = A[i]; // 更新最大值
else if (A[i] < Min) Min = A[i]; // 更新最小值
if (A[i] >= 0) res[i] = A[i] * Max; // 根据A[i]的正负性选择相乘的数
else res[i] = A[i] * Min;
}
}
（3）时间复杂度为 O (n)；空间复杂度为 O (1)。