1) 算法的基本思想

该算法的核心目标是为数组res的每个位置i找到从i到数组末尾的所有可能乘积中的最大值。为了高效实现这一目标，我们可以采用从后向前遍历数组的方法。具体来说，从数组的最后一个元素开始，逐步向前处理每个元素，同时维护一个当前最大值max_val。对于每个位置i，我们比较当前元素A[i]自身的值以及它与下一个位置的max_val的乘积，取两者中的较大值作为新的max_val，并将其存入res[i]中。这样可以确保每个位置i的res[i]存储的是从i到数组末尾的所有可能乘积的最大值。

2) 用 C/C++ 描述算法

#include <algorithm> // 用于std::max函数

void CalMulMax(int A[], int res[], int n) {
    if (n <= 0) return; // 处理边界情况
    
    // 初始化最后一个元素
    res[n-1] = A[n-1];
    int max_val = A[n-1]; // 从最后一个元素开始
    
    // 从倒数第二个元素向前遍历到第一个元素
    for (int i = n-2; i >= 0; --i) {
        // 计算当前元素与后续最大值的乘积
        int product = A[i] * max_val;
        // 更新当前最大值
        max_val = std::max(A[i], product);
        // 将当前最大值存入结果数组
        res[i] = max_val;
    }
}

3) 时间、空间复杂度分析

• 时间复杂度：该算法只需要对数组进行一次反向遍历，因此时间复杂度为 O (n)，其中 n 是数组的长度。

• 空间复杂度：算法只使用了常数级的额外空间（仅一个变量max_val），因此空间复杂度为 O (1)，这意味着算法在空间上是高效的。