2025·41 后缀最大乘积：从逐个后缀扫描到反向一遍

本文属于「从暴力解到最优解」专题。套路照旧：先把暴力解写对 → 按判分口径估分 → 找浪费 → 升级成最优解。

题目

设有两个长度均为 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 分）

总分 13 分。注意题面的「尽可能高效」这次带了双限定——时间和空间都在要求里，这在后面判分时会各管一档。

第一步：把暴力解写对

题意直译：res[i] 是「A[i] 乘上后缀 A[i..n−1] 里某个元素」能得到的最大乘积。注意 j 的范围从 i 起步，j = i 也合法，所以 res[i] 至少包含 A[i] × A[i] = A[i]² 这一项——题面例子里 res[2] = 81 = (−9)² 就是这么来的。

考场上最自然的第一反应：对每个 i，把 j 从 i 扫到 n−1，所有乘积都算出来打擂台。这个写法有个好处——什么性质都不用想：正数负数、j = i 的自乘，全被「每个都试」自动覆盖：

void calMulMax(int A[], int res[], int n) {
    for (int i = 0; i < n; i++) {
        int best = A[i] * A[i];            // j = i 起步：至少有 A[i]² 这一项
        for (int j = i + 1; j < n; j++) {  // 向后扫整段后缀
            int p = A[i] * A[j];
            if (p > best) best = p;
        }
        res[i] = best;
    }
}

拿题面的例子验证 A = {1, 4, −9, 6}：i=0 试 1, 4, −9, 6 得最大 6；i=1 试 16, −36, 24 得 24；i=2 试 81, −54 得 81；i=3 只有 36。res = {6, 24, 81, 36} ✓，连负数的情形都对——(−9) 的最优搭档是它自己。

复杂度：双层循环，时间 $O(n^2)$；只有几个标量，辅助空间 $O(1)$。有点意思的是，这份暴力解空间已经达标，卡的只有时间。

它值多少分

按正确性/最优性两个维度（详见总纲）：

• 正确性：全枚举不漏任何 (i, j) 组合，结果必然正确；j = i 的边界自动覆盖；复杂度照实写 $O(n^2)$、$O(1)$。正确性维度的分拿得到。
• 最优性：题面「时间和空间上尽可能高效」，期望是时间 $O(n)$ + 辅助空间 $O(1)$。暴力解空间过关，时间差一个量级，最优性拿不到。

这道 13 分的题，暴力解拿正确性分、丢最优性分，主体分在手。往下走之前记住题面那个双限定——升级时间的时候，别把已经达标的空间又赔进去。

暴力解的浪费在哪

用总纲的三个问题审一遍：

**有没有重复扫描？——有，教科书级别的。**i 的后缀 A[i..n−1] 和 i+1 的后缀 A[i+1..n−1] 只差一个元素 A[i]，暴力解却把两段后缀各自从头扫到尾。i 每往左挪一格，几乎整段后缀被原样重扫一遍，累计约 n²/2 次乘法里绝大多数在重复劳动。

要消除重扫，先想清楚一个问题：**一段后缀里，我到底需要什么信息？**res[i] = A[i] × A[j] 的最大值，A[i] 这轮是固定的：

• A[i] ≥ 0 时，乘积要大，挑后缀里最大的数；
• A[i] < 0 时，负负得正——挑后缀里最小的数（绝对值最大的负数），乘出来反而是最大的正值。

所以每段后缀只需要两个数：max 和 min。有了它们，res[i] 在 $O(1)$ 内就能算出。而这两个数恰好可以增量维护——后缀向左长一个元素，新 max/min 就是旧值和 A[i] 比一下的结果。重扫的必要性彻底消失。

智慧化改造：反向一遍，顺手维护 max/min

先看一个容易想到的中间方案：预处理出两个数组 sufMax[]、sufMin[]（各存每个位置的后缀最大/最小），再正着扫一遍算 res。时间确实降到 $O(n)$ 了——但两个辅助数组是 $O(n)$ 空间，题面把空间也框进了「尽可能高效」，第 (3) 问会在空间上丢分。这正是这道题的精髓：「算后缀极值」和「算 res」要合并进同一次反向扫描，辅助空间只留两个标量。

从 i = n−1 出发向左推进，维护 curMax = max(A[i..n-1])、curMin = min(A[i..n-1])；每轮先把 A[i] 纳入这两个值，再算 res[i]：

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]。顺序反了，curMax/curMin 里没有 A[i]，j = i 的 A[i]² 这一项就漏了——暴力解里 j 从 i 起步天然覆盖的东西，升级后要靠更新顺序自己保证。
• 边界 res[n−1] 显式初始化为 A[n−1]²：i = n−1 时 j 只能取 n−1，而且此时 curMax/curMin 还没有值可用。
• 两个乘积都要试：只算 A[i] × curMax，在 A[i] < 0 且后缀含负数时会把正确答案（负×负）漏掉。curMin 的存在就是为负数情形准备的。
• 溢出：|A[i]| 很大时乘积可能超出 int，工程上应改 long long；阅卷一般不深究，卷面提一句更稳。

复杂度：单趟反向扫描，循环 n−1 次，每轮常数次比较和乘法，时间 $O(n)$；辅助空间只有 curMax、curMin 等几个标量，$O(1)$——A 和 res 是题目给定的输入输出，不计入辅助空间。第 (3) 问要把「A/res 不计入」这层口径写明，空间答成 $O(n)$ 就把题面的「空间高效」理解偏了。

两版对照跑一遍

用题面的例子 A = [1, 4, -9, 6]（res = [6, 24, 81, 36]），先看暴力解——每个 i 都把后缀原样重扫：

加载可视化中...

再看反向扫描版——一遍从右到左，curMax/curMin 一路顺手更新，每个 res[i] 两次乘法就出结果：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

等价方法与升级空间

• 后缀数组预处理版：先 $O(n)$ 算出 sufMax/sufMin 两个数组再扫一遍算 res。时间达标、结果正确，但 $O(n)$ 辅助空间违反题面「空间尽可能高效」的要求，第 (3) 问丢分。它和满分解之间只差「把两遍合成一遍」这一步，值得作为思维台阶但别停在这。
• 手段归档：反向扫描顺手维护后缀极值，是总纲「找浪费」第一问（重复扫描）的标准对策——一遍扫描时多记一点。2018·41 的标记数组记的是「见过谁」，这道题记的是「后缀极值」，方向相反（那题正着扫、这题反着扫），肌肉是同一块。

下一步

• 在 OJ 上把两版代码都提交跑一遍：ds-2025-41 后缀最大乘积
• 回到题库看这道题的完整解析与错因：真题库 · 数据结构