设有两个长度均为 n 的一维整型数组 A 和 res，对数组 A 中的每个元素 A[i]，计算 A[i] 与 A[j](0 ≤ i ≤ j ≤ n-1) 乘积的最大值，并将其保存到 res[i]中。例如，若 A[i] = {1, 4, -9, 6}，则得到 res[i] = {6, 24, 81, 36}。现给定数组 A，请设计一个时间和空间上尽可能高效的算法 calMulMax，求 res 中各元素的值。函数原型为：void calMulMax(int A[], int res[], int n)，要求：

(1) 给出算法的基本设计思想：（4 分）

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释：（7 分）

(3) 说明你所设计算法的时间复杂度和空间复杂度。（2 分）

顺序表

[tag_link]

1）若 A[i] 为负数的话，则 A[j] 为子数组 A[i:n] 中的最小值时，A[i] * A[j] 为最大值。若 A[i] 为正数的话，则 A[j] 为子数组 A[i:n] 中的最大值时，A[i] * A[j] 为最大值。因此算法步骤如下：

1. 从右到左遍历数组 A：

• 维护一个变量 maxValue 来存储当前从 i 到 n-1 范围内的最大值。
• 维护一个变量 minValue 来存储当前从 i 到 n-1 范围内的最小值。
• 在每次迭代中，更新 maxValue 和 minValue。
• 计算 A[i] * maxValue 和 A[i] * minValue，并将它们的较大值存储在 res[i] 中。

2. 更新 maxValue 和 minValue：在每次迭代中，maxValue 是当前元素与之前的 maxValue 的较大值，minValue 是当前元素与之前的 minValue 的较小值。

2）算法实现如下：

void calMulMax(int A[], int res[], int n) {
    int minValue = INT32_MAX;
    int maxValue = INT32_MIN;
    for (int i = n-1; i >= 0; i--) {
        if (A[i] < minValue) {
            minValue = A[i];
        }
        if (A[i] > maxValue) {
            maxValue = A[i];
        }
        if (A[i] > 0) {
            res[i] = A[i] * maxValue;
        } else {
            res[i] = A[i] * minValue;
        }
    }
}

3）算法的时间复杂度为 O(n)，空间复杂度为 O(1)。