1) 算法的基本思想

我们需要计算数组 A 中每个元素 A[i] 与 A[i] 到 A[n-1] 之间某个元素 A[j]（其中 i ≤ j）的乘积的最大值，并将这个最大值存入 res[i] 中。换句话说，对于每个 i，res[i] 是 max(A[i] * A[j])（其中 j 从 i 到 n-1）。
2）void CalMulMax(int A[], int res[], int n) { if (n == 0) return; // 处理空数组的情况 // 预先计算 max_suffix 数组 int* max_suffix = new int[n]; // 动态分配内存 max_suffix[n-1] = A[n-1]; // 最后一个元素的最大值就是它自己 // 从右向左计算 max_suffix for (int i = n-2; i >= 0; --i) { max_suffix[i] = (A[i] > max_suffix[i+1]) ? A[i] : max_suffix[i+1]; } // 计算 res[i] = A[i] * max_suffix[i] for (int i = 0; i < n; ++i) { res[i] = A[i] * max_suffix[i]; } delete[] max_suffix; // 释放动态分配的内存 }
3）

• 时间复杂度：O(n)

  • 计算 max_suffix 数组需要 O(n) 时间（从右向左遍历一次）。
  • 计算 res 数组需要 O(n) 时间（遍历一次）。
  • 总时间为 O(n) + O(n) = O(n)。

• 空间复杂度：O(n)

  • 需要额外的 max_suffix 数组，大小为 n。
  • 其他空间（如循环变量）是常数空间，可以忽略。
  • 总空间为 O(n)。