面试题42：连续子数组的最大和

从“负债是否值得带到下一天”开始

先预测：扫描1、-2、3时，到达3之前累计和是-1。若把-1带上，得到2；若丢掉历史、从3重新开始，得到3。任何负的前缀都会拖低同一个后缀，因此最优连续段经过当前位置时，只需在“延续旧段”和“当前重启”之间选择。

这就是“连续子数组的最大和”的线性核心。作者没有保存所有区间，只用 nCurSum 表示当前子数组和，用 nGreatestSum 保存到目前为止所有结尾位置的全局最大值。

作者为何在当前和不正时重启

若前一位置的结尾最优大于0，拼接当前值一定比单独当前值更大，所以延续。若前一结尾最优小于0，拼接后更小，应该从当前值重新开始。常见总结是“当前累加和为负则重新开始”，作者源码实际使用小于等于0。

当前和等于0时，延续与重启得到相同数值；作者选择重启，因此会向右移动。只返回最大和时两种选择等价；若还要返回区间，等于0时的策略会影响同和答案是最长、最短还是最靠右。

#include <cstdio>
 
bool g_InvalidInput = false;
 
int FindGreatestSumOfSubArray(
    int* pData, int nLength) {
    if (pData == nullptr || nLength <= 0) {
        g_InvalidInput = true;
        return 0;
    }
 
    g_InvalidInput = false;
 
    int nCurSum = 0;
    int nGreatestSum = 0x80000000;
    for (int i = 0; i < nLength; ++i) {
        if (nCurSum <= 0) {
            nCurSum = pData[i];
        } else {
            nCurSum += pData[i];
        }
 
        if (nCurSum > nGreatestSum) {
            nGreatestSum = nCurSum;
        }
    }
    return nGreatestSum;
}

循环不变量是：处理完下标i后，nCurSum是所有以i结尾的非空连续子数组中的最大和；nGreatestSum是所有结束位置不超过i的非空连续子数组最大和。当前值单独成段与前一结尾最优加当前值涵盖了以i结尾的全部可能，因为任何更早起点都已被前一状态压缩。

每个元素读取一次，时间O(n)；只保留两个和，额外空间O(1)。这就是一维的空间压缩，不是缺少状态定义的“贪心猜测”。

混合数组逐步扫描

作者Test1是1、-2、3、10、-4、7、2、-5。最大段从下标2开始，到下标6结束，元素为3、10、-4、7、2，总和18。源码只返回18；图中为教学额外追踪了起点与最佳区间。

到-4时当前和从13降到9，但仍为正，所以不能看到负值就立刻重启。这个9会帮助后续7和2达到18。正确判断对象是“加入当前值之前的累计贡献是否值得保留”，不是“当前元素是否为负”。

到最后-5时当前和仍有13，却没有超过历史18。若只返回循环结束时的nCurSum，会错误得到13；因此当前状态与全局状态必须分开。

全负数组与非空约束

题目要求的是非空连续子数组。这个决定了全负数组不能返回0；必须选最大单个元素。

作者把nGreatestSum初始化为 0x80000000，在目标Visual C++的32位int语义下得到最小整数。于是-2、-8、-1、-5、-9逐项重启，best最终更新为-1。若best错误初始化为0，所有负current都无法刷新它，就等价于偷偷允许空子数组。

更可移植的写法是 std::numeric_limits<int>::lowest()，或先验证输入后直接以首元素初始化current和best，再从第二项扫描。十六进制字面量 0x80000000 的类型取决于int宽度和可表示范围，转成int可能是实现定义行为，不应作为跨平台最低值写法。

作者返回值和全局状态

空指针或长度不正时，作者返回0并把设为true。有效调用先清为false。合法数组的最大和也可能是0，例如-1、0、-2，因此调用者必须同时读取返回值和标志。

全局标志让接口不可重入：并发调用可能在一个线程读结果前被另一个线程覆盖。返回结构、optional或expected能把值与状态绑定。current加当前元素还可能发生有符号int溢出；若输入和长度允许超出int和，应使用int64_t并做边界检查。

作者的函数不返回区间。工程需求若要展示起止位置，需要在每次重启时记录candidateStart，在best刷新时复制candidateStart和当前下标。等和时是否更新决定并列策略，必须写进契约。

#include <cstddef>
#include <cstdint>
#include <optional>
#include <vector>
 
struct GreatestRange {
    std::int64_t sum;
    std::size_t begin;
    std::size_t end;
};
 
std::optional<GreatestRange>
greatestSubarray(const std::vector<int>& values) {
    if (values.empty()) {
        return std::nullopt;
    }
 
    std::int64_t current = values[0];
    std::int64_t best = values[0];
    std::size_t currentBegin = 0;
    GreatestRange result{best, 0, 0};
 
    for (std::size_t i = 1;
         i < values.size(); ++i) {
        if (current <= 0) {
            current = values[i];
            currentBegin = i;
        } else {
            current += values[i];
        }
 
        if (current > best) {
            best = current;
            result = {best, currentBegin, i};
        }
    }
    return result;
}

这版保持作者“等于0也重启”和“只在严格更大时刷新”的并列政策：它偏向最早发现的最大和区间，但零前缀后会选择更靠右的起点。若要求最长区间或字典序最小区间，要在等和分支增加明确比较。

与显式递推式的对应

设ending[i]为必须以i结尾的最大非空和，则它等于当前值与ending[i-1]加当前值中的较大者。作者先判断旧current是否大于0，正是把这个max选择展开为分支。

answer[i]是前i项内的全局最大和，等于answer[i-1]与ending[i]的较大者。因为下一步只依赖前一ending与answer，完整数组可以压缩成current和best两个标量。

“负前缀应丢弃”也可用交换论证：假设一个最优段包含某个和为负的前缀，删除该前缀后仍连续且和更大，矛盾。和为0的前缀删除后和相同，所以是否删除只影响区间政策，不影响最大值。

对环形数组、允许删除一个元素、限制长度上下界等变体，这个两状态递推不再直接成立。必须重新定义状态或用前缀和、单调队列；不能只改一行重启条件。

作者四组测试的准确语义

Test同时比较整数返回值与g_InvalidInput：

1. 混合数组1、-2、3、10、-4、7、2、-5，期望18与false。
2. 全负数组-2、-8、-1、-5、-9，期望-1与false。
3. 全正数组2、8、1、5、9，期望25与false。
4. nullptr, 0，期望0与true。

全正用例要求持续延续到整个数组；全负用例要求每步重启且不允许空段；混合用例同时覆盖负贡献保留与丢弃。源码没有单元素、零、含零并列、正负极值、非空指针零长度或区间恢复测试。

可靠扩展测试应加入0、-1/0/-2、单个最小整数、多个等和最佳段，并用O(n²)枚举所有非空区间作为短数组参考。暴力参考逻辑与线性算法不同，适合做随机差分。

#include <cassert>
#include <cstdint>
#include <vector>
 
std::int64_t bruteGreatest(
    const std::vector<int>& values) {
    std::int64_t best = values.front();
    for (std::size_t begin = 0;
         begin < values.size(); ++begin) {
        std::int64_t sum = 0;
        for (std::size_t end = begin;
             end < values.size(); ++end) {
            sum += values[end];
            if (sum > best) {
                best = sum;
            }
        }
    }
    return best;
}
 
void testGreatestSubarray() {
    assert(greatestSubarray({}).has_value() == false);
    assert(greatestSubarray({-2,-8,-1,-5,-9})
               ->sum == -1);
    assert(greatestSubarray({2,8,1,5,9})
               ->sum == 25);
    assert(greatestSubarray({-1,0,-2})
               ->sum == 0);
    assert(greatestSubarray(
        {1,-2,3,10,-4,7,2,-5})->sum == 18);
}

随机生成短数组时，先确保非空，比较线性结果sum与bruteGreatest。区间结果还应断言begin不大于end、区间求和等于sum，并验证没有其他区间更大。

流式与并行边界

只求最大和时，current和best可以随数据流在线更新，不必保存全部历史；若要返回区间元素，则至少保存索引，若流无法回放还要保留最佳段内容或外部位置引用。

多个分片不能只取各自最大子数组再求最大，因为全局最优可能跨分片边界。可合并摘要需要总和、最大前缀和、最大后缀和、最大子数组和四项；合并两个摘要时，跨界候选是左最大后缀加右最大前缀。这个结构可用于并行归约和线段树。

并发在线更新必须串行化顺序，因为连续子数组定义依赖元素次序。若事件可能乱序到达，应先按序列号重排或定义窗口时间顺序；直接按到达顺序更新会计算另一个序列的答案。

监控系统还要防止无限累加溢出。即便单个输入是32位，长正序列总和也可能远超int；64位仍需评估业务上限，必要时使用饱和策略、大整数或显式错误状态。

若业务改成“最近w个元素内的最大连续子数组”，旧current不能在元素过期时逆向撤销：过期值可能位于当前候选段中间，也可能决定历史best。此时要用可删除的前缀和结构、分块摘要或线段树，并把窗口边界纳入状态。无限历史的线性扫描与固定窗口查询虽然题面相似，状态可逆性完全不同。

返回区间时还要区分元素下标与流偏移。若输入批次被压缩或丢弃，begin和end必须绑定单调序列号；仅保存批内下标会在下一批重复。日志审计通常还需保存触发best刷新的时间和输入版本，确保离线重放能得到同一段。

本章练习

概念说明

本章核心概念包括：动态规划，全负数组。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. current表示必须以当前位置结尾的最大非空连续子数组和。
2. 此前current大于0时延续，不正时从当前元素重启。
3. best独立保存所有结尾位置中的全局最大值。
4. 作者在current等于0时也重启，最大和不变但区间政策改变。
5. 全负数组受非空约束，答案是最大单元素而不是0。
6. 时间O(n)、额外空间O(1)，是动态规划的状态压缩。
7. 作者以0和全局无效标志表达失败，现代接口应绑定值与状态。
8. 最低整数初始化和累加溢出需要可移植类型与边界设计。

名词解释