第41题
(本题 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)。