数据结构
2025-41
设有两个长度均为 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);要求：
- 给出算法的基本设计思想；
- 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释；
- 说明你所设计算法的时间复杂度和空间复杂度。
答案
(1) 基本设计思想
从右向左扫描数组，同时维护当前位置及其右侧元素的最小值 minSuffix 和最大值 maxSuffix。若 A[i] 非负，则与后缀最大值相乘可取得最大乘积；若 A[i] 为负，则与后缀最小值相乘可取得最大乘积。
(2) 算法
void CalMultMax(int A[], int res[], int n)
{
if (n <= 0) return;
int minSuffix = A[n - 1];
int maxSuffix = A[n - 1];
for (int i = n - 1; i >= 0; --i) {
if (A[i] < minSuffix) minSuffix = A[i];
if (A[i] > maxSuffix) maxSuffix = A[i];
if (A[i] >= 0)
res[i] = A[i] * maxSuffix;
else
res[i] = A[i] * minSuffix;
}
}(3) 复杂度
时间复杂度为 O(n)，额外空间复杂度为 O(1)。