题目

设有两个长度均为 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) 设计思想 [4 分]

问题转化。对每个下标 i，要求的是

由于 A[i] 是这一轮的固定常数，问题就变成「在 这段后缀里，挑一个 使得 最大」。

关键洞察：负数乘负数为正。如果 A[i] ≥ 0，要让乘积最大就挑后缀里最大的那个数；但如果 A[i] < 0，挑后缀里最小（即绝对值最大的负数）反而能得到最大正值。所以只需要同时知道后缀的最大值和最小值，就能在 O(1) 内算出 res[i]。

怎么避免每次都重新扫描后缀？反向遍历。从右往左推进 i：

• 维护两个变量 curMax = max(A[i..n-1])、curMin = min(A[i..n-1])；
• i 从 n-1 出发，初始 curMax = curMin = A[n-1]；
• 每次 i 减 1，新元素 A[i] 加入后缀，更新 curMax = max(curMax, A[i])、curMin = min(curMin, A[i])；
• 算 res[i] = max(A[i] * curMax, A[i] * curMin)。

整个过程每个下标只访问一次，O(n) 完成，额外空间只有两个标量。

编者注（生僻术语）：题目里的「j ≥ i」隐含了 j = i 也合法，即 res[i] 至少包含 A[i] · A[i] = A[i]² 这一项。下面的循环用「先更新 curMax/curMin 再算 res[i]」就自然把 j = i 这种情况覆盖掉了。

(2) 代码实现 [7 分]

void calMulMax(int A[], int res[], int n) {
    if (n <= 0) return;                       // 边界：空数组直接返回

    int curMax = A[n - 1];                    // 后缀 A[i..n-1] 的最大值
    int curMin = A[n - 1];                    // 后缀 A[i..n-1] 的最小值
    res[n - 1] = A[n - 1] * A[n - 1];         // i=n-1 时 j 只能取 n-1，结果为 A[n-1]²

    for (int i = n - 2; i >= 0; i--) {
        // 把 A[i] 纳入后缀，更新最大/最小
        if (A[i] > curMax) curMax = A[i];
        if (A[i] < curMin) curMin = A[i];

        // A[i] 既可能正也可能负，两种乘法都试一下取大者
        int p1 = A[i] * curMax;
        int p2 = A[i] * curMin;
        res[i] = (p1 > p2) ? p1 : p2;
    }
}

关键点说明：

• 更新顺序很重要：必须先把 A[i] 纳入 curMax/curMin，再算 res[i]，否则当 j = i 时（也就是 res[i] 至少要考虑 A[i]·A[i]）会被漏掉。
• 不需要预处理后缀数组：朴素做法是先 O(n) 算出后缀 max 和后缀 min 数组，再 O(n) 算 res——这样要 O(n) 额外空间。本算法把"算后缀极值"和"算 res"合并到同一次反向扫描里，省下了那两个辅助数组。
• 乘法溢出：若 |A[i]| 较大（例如接近 2³¹），两数相乘可能溢出 int。考研评分对此一般不深究，但工程上应改用 long long。

(3) 复杂度分析 [2 分]

• 时间复杂度 ：循环执行 n - 1 次，每次循环内部只有常数次比较和算术运算，总时间为 。
• 空间复杂度 ：除入参 A、res 外，只用了 curMax、curMin、p1、p2、i 五个标量，与 n 无关。

编者注（生僻术语）：题目说"时间和空间上尽可能高效"，这里的"空间"指的是辅助空间——A 和 res 是题目给定的输入输出，不计入算法本身的空间开销。这道题的标准答卷必须写到 O(1) 辅助空间才能拿满分；如果只做到"先算两个后缀数组再扫"那种 O(n) 辅助空间，第 (3) 问会丢分。