解法一:暴力解（双重循环)

1)算法的基本思想
使用两个嵌套的for循环遍历数组A的所有可能的(i, j)组合，其中0≤i≤ j ≤ n-1。对于每个i，遍历所有j ≥ i，计算A[i]*A[j]，并记录其中的最大值到res[i]中。

2)C代码实现

//暴力破解法实现
void calMulMax ( int A[], int res [], int n)
{
    for(int i =0; i < n; i++)   //遍历每个起始位置i
    {
        int maxMul = A[i]*A[i];
        //初始化
        for (intj=i; j< n; j++)  //遍历所有j>= i
        {
            int currentMul = A[i]~ A[j];
            if ( currentMul > maxMul)   //当前乘积更大,更新
            {
                maxMul =currentMul;
            }
        }
        res [i]= maxMul; //将最大乘积存入res[i]
    }
}

3)时间、空间复杂度
时间复杂度:O(n^2)，因为使用了两个嵌套的for循环。

空间复杂度:O(1)，使用了常数级别的额外空间。

解法二：使用辅助数组 B 和 C

1)算法的基本思想
预先计算并存储从每个位置 i 到数组末尾 n - 1 之间的最大值 B [i] 和最小值 C [i]。对于每个元素 A [i]：

• 如果 A [i] 为非负数，则最大的乘积为 A [i] * B [i]。
• 如果 A [i] 为负数，则最大的乘积为 A [i] * C [i]。

这样可以在一次遍历中预处理 B 和 C，然后在另一次遍历中计算 res 数组。

2)C 代码实现

// 使用辅助数组B和C的实现
void CalMulMax(int A[], int res[], int n) {
    int B[n]; // B[i]表示A[i..n - 1]中的最大值
    int C[n]; // C[i]表示A[i..n - 1]中的最小值
    // 从后向前遍历，填充B和C数组
    B[n - 1] = A[n - 1];
    C[n - 1] = A[n - 1];
    for(int i = n - 2; i >= 0; i--) {
        B[i] = max(B[i + 1], A[i]);
        C[i] = min(C[i + 1], A[i]);
    }
    // 计算res数组，最大值只可能是A[i]*B[i]或A[i]*C[i]
    for(int i = 0; i < n; i++)
        res[i] = max(A[i]*B[i], A[i]*C[i]);
}

3)时间、空间复杂度
时间复杂度：O (n)，因为预处理 B 和 C 数组各需一次线性遍历，计算 res 数组也只需一次线性遍历。
空间复杂度：O (n)，需要额外的两个辅助数组 B 和 C，每个大小为 n。

解法三：使用辅助变量B和C

1)算法的基本思想
只需要在解法二的基础上，只需要用变量存最小值和最大值即可。

简单函数 / 值（直接调用）

注：还有其他的诸如栈和队列的操作函数也可以直接使用。
输入输出有三种写法都可以：① scanf ()/printf () ② cin/cout ③ 写中文。

2)C 代码实现

// 使用辅助数组 B 和 C 的实现
void CalMulMax(int A[], int res[], int n) {
    int B; // B 表示 A[i..n-1] 中的最大值
    int C; // C 表示 A[i..n-1] 中的最小值
    B = A[n - 1];
    C = A[n - 1];
    res[n - 1] = A[n - 1] * A[n - 1];
    // 计算 res 数组，最大值只能是 A[i]*B[i] 或 A[i]*C[i]
    for (int i = n - 2; i >= 0; i--) {
        B = max(B, A[i]);
        C = min(C, A[i]);
        res[i] = max(A[i] * B, A[i] * C);
    }
}

3)时间、空间复杂度
时间复杂度: O (n)。
空间复杂度: O (1)。