思路。标准的「Kadane + 记录区间」：维护 \(cur\)（以当前元素结尾的最大和）、\(best\)（历史最优）、以及当前段左端点 \(l\)。当 \(cur \lt 0\) 时，带着它只会拖累后面的任何段，于是在当前位置重开一段；更新 \(best\) 时同步记录 \([l, r]\)。用数组 \([-2, 1, -3, 4, -1, 2, 1, -5, 4]\) 手算一遍（1 下标）：

答案是和为 6，区间 \([4,7]\)，即子数组 \([4,-1,2,1]\)。

代码。

struct Result { long long sum; int l, r; };   // 闭区间 [l, r]，0 下标

Result maxSubarray(const vector<int>& a) {
    long long cur = 0, best = LLONG_MIN;      // best 初始化为 -inf，兼容全负数组
    int l = 0, bestL = 0, bestR = 0;
    for (int r = 0; r < (int)a.size(); ++r) {
        if (cur < 0) { cur = 0; l = r; }      // 负前缀只会拖累：从 r 重新开段
        cur += a[r];
        if (cur > best) { best = cur; bestL = l; bestR = r; }
    }
    return {best, bestL, bestR};
}

复杂度。时间 \(O(n)\)，一遍扫描；空间 \(O(1)\)。

边界。空数组需要和面试官确认（返回什么）；单元素返回自身；全负数组返回最大的单个元素（因为 \(best\) 从 \(-\infty\) 起步，永不被「空段和 0」污染）；元素绝对值接近 \(10^9\)、长度 \(10^5\) 时累加和超出 int 范围，用 long long。

面试怎么讲。先说状态定义「以 i 结尾的最大和」，再给一行转移，最后主动提区间版只需多记两个下标。手算表能极大增强可信度，建议至少口算前四个位置。

思路。与例题 1 同型，仅输出不同：只返回和，不需要下标。题库自带的解法是：设 \(max\_sum\) 与 \(current\_sum\)，遍历数组，若 \(current\_sum \ge max\_sum\) 则更新，若 \(current\_sum\) 变负则清零。这个描述的隐患有两处：一是没有交代 \(max\_sum\) 的初值——若初始化为 0，等于默认允许空子数组，全负数组会错误地返回 0；二是「先比较再清零」的顺序必须保持，若先清零再比较，会把恰好为 0 的段处理错。用 \(a_1\) 同时初始化两者即可同时修掉两个坑。

代码。

int maxSubArray(const vector<int>& a) {       // 经典 Kadane：只返回和
    int best = a[0], cur = a[0];              // 用 a[0] 初始化，全负数组也正确
    for (size_t i = 1; i < a.size(); ++i) {
        cur = max(a[i], cur + a[i]);          // 以 i 结尾的最优：接上前段或另起一段
        best = max(best, cur);
    }
    return best;
}

复杂度。时间 \(O(n)\)，空间 \(O(1)\)。

边界。约定子数组非空，则 \(n \ge 1\)；全负输入如 \([-3,-1,-4]\) 返回 −1 而非 0。若面试官明确允许空子数组，把 best 初始化为 0 即可，先问口径再写代码是加分动作。

面试怎么讲。主动复述那份伪代码并指出两处隐患（初值口径、比较与清零的顺序），比直接写出正确版本更能展示你读代码的能力。源题在这道编程题后面还挂了一串金融与统计追问（过拟合、蒙特卡洛、Black–Scholes、期权对冲、bootstrapping 与 swap curve），它们属于金融直觉板块，去向见本章「误区与边界」末尾的交叉引用。

思路。先做一次等价转化：「存在和为正的子数组」当且仅当「最大子数组和为正」。必要性显然（那段本身就是候选）；充分性同样成立：若最大和 \(best \gt 0\)，取得 \(best\) 的那段就是所求。于是问题归约为 Kadane，只需在最后把「返回 \(best\)」改成「返回 \(best \gt 0\)」，要输出具体区间时复用例题 1 的下标记录。这类「先证等价、再复用已验证的算法」的路径，是面试里处理陌生措辞的通用方法。

代码。

bool hasPositiveSubarray(const vector<int>& tx) {  // 等价于最大子数组和是否为正
    long long best = LLONG_MIN, cur = 0;
    for (int x : tx) {
        cur = max((long long)x, cur + x);     // Kadane 内核不变
        best = max(best, cur);
    }
    return best > 0;                          // 输出层从「返回和」改成「判定」
}

复杂度。时间 \(O(n)\)，空间 \(O(1)\)。

边界。全正数组返回 true 且任意单元素段都可行；全非正数组返回 false；若要求「恰好和为某个给定值」而不仅是正数，则等价转化失效，需要前缀和 + 哈希（例题 5 的方法）。

面试怎么讲。把等价性证明放在代码前面讲：一句「和为正的存在性由最大和的符号完全刻画」即可。追问变式：「找和最大的非空段且长度不超过 k」需要前缀和加单调队列，可引到 033 章。

思路（连续版）。「最长的严格递增连续段」只需一遍扫描：维护当前段长 \(cur\)，\(a_i \gt a_{i-1}\) 时延长，否则重置为 1。用 \(f_i = f_{i-1} + 1\)（若递增）否则 \(f_i = 1\) 的 DP 语言说出来也行，但它退化为常数状态。

代码（连续版）。

int longestIncreasingRun(const vector<int>& a) {  // 连续版：一遍扫描
    if (a.empty()) return 0;
    int best = 1, cur = 1;
    for (size_t i = 1; i < a.size(); ++i) {
        cur = (a[i] > a[i - 1]) ? cur + 1 : 1;    // 严格递增才延长，否则重置
        best = max(best, cur);
    }
    return best;
}

思路（一般版，\(O(n^2)\)）。状态 \(f_i\) 为以 \(a_i\) 结尾的 LIS 长度，按前文转移式枚举前驱 \(j\)。它好写、好证，是面试的第一落点；数组规模到 \(10^5\) 时再升级。

代码（一般版 \(O(n^2)\)）。

int lisQuadratic(const vector<int>& a) {     // O(n^2) DP：先保证正确再谈优化
    int n = (int)a.size(), ans = 0;
    vector<int> f(n, 1);                       // f[i]：以 a[i] 结尾的 LIS 长度
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j)
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);
    }
    return ans;
}

代码（一般版 \(O(n \log n)\)）。tails 数组 + lower_bound，构造过程见下表（输入 \([1,2,6,3,2,4]\)）：

int lisFast(const vector<int>& a) {          // O(n log n)：贪心 + 二分
    vector<int> tails;                         // tails[k]：长度 k+1 的 LIS 的最小结尾
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);  // x 能把最长长度推高 1
        else *it = x;                          // 换成更小的结尾，给后续留空间
    }
    return (int)tails.size();
}

复杂度。连续版 \(O(n)\)；一般版 \(O(n^2)\) 与 \(O(n \log n)\) 两档，后者每个元素一次二分。

边界。\([1,2,2,3]\)：严格递增的答案是 \([1,2,3]\)（长度 3），lower_bound 版返回 3 ✓，若误用 upper_bound 返回 4 ✗——相等元素的处理是最常见的追问点。空数组返回 0；全相同元素如 \([5,5,5]\) 严格 LIS 为 1。若题目要求输出子序列本身，\(O(n^2)\) 版倒着回溯 \(f\) 的前驱最直接；\(O(n \log n)\) 版要额外记录每个元素替换的位置再回溯。

面试怎么讲。按「连续版一遍扫描 → 一般版 \(O(n^2)\) DP → 需要更快吗？→ tails + 二分」的顺序推进，每一档都先给复杂度再写代码；最后主动指出严格 / 非严格与 lower_bound / upper_bound 的对应。

思路。前缀和把区间和变成两点差：定义 \(P_0 = 0\)、\(P_i = a_1 + \cdots + a_i\)，则子数组 \((l, r]\) 的和为 \(P_r - P_l\)。它等于 0 当且仅当 \(P_r = P_l\)——「找和为 0 的子数组」等价于「找两个位置的前缀和相等」。于是从左到右扫一遍，用哈希表记录每个前缀和值首次出现的下标；再次遇到同一个值时，两者之间的子数组和为 0，用「当前下标 − 首次下标」更新最长。只记首次出现，是因为首次出现离后来者最远，区间才可能最长。存在性版本更简单：只要某个前缀和值出现两次，或数组里出现 0，答案即为是。

手算 \([4, -1, -1, -1, 3]\)：前缀和序列为 \(0, 4, 3, 2, 1, 4\)。值 4 出现在下标 1 与 4（前缀和数组的 0 下标从 \(P_0\) 起算），对应子数组下标 2 到 4（1 下标），即 \([-1,-1,-1,3]\)，长度 4，和恰为 0。

代码。

// 返回 {最长长度, 起点下标}；不存在和为 0 的子数组时长度为 0
pair<int, int> longestZeroSum(const vector<int>& a) {
    unordered_map<long long, int> first;      // 前缀和 -> 首次出现下标
    long long s = 0;
    int bestLen = 0, bestL = -1;
    first[0] = -1;                             // 空前缀 P[0] = 0 记在 -1
    for (int i = 0; i < (int)a.size(); ++i) {
        s += a[i];
        auto it = first.find(s);
        if (it != first.end()) {               // 同一前缀和两次出现：中间一段和为 0
            if (i - it->second > bestLen) { bestLen = i - it->second; bestL = it->second + 1; }
        } else first[s] = i;                   // 只记首次出现，区间才可能最长
    }
    return {bestLen, bestL};
}

复杂度。时间 \(O(n)\)（哈希均摊），空间 \(O(n)\)。

边界。必须预置 \(first[0] = -1\)，否则「从数组开头开始的零和段」（如 \([1,-1]\)）会被漏掉。前缀和可能溢出 int，用 long long。变式「和等于 k 的最长子数组」完全同构：找 \(P_r - P_l = k\)，即查 \(s - k\) 是否出现过。

面试怎么讲。先写前缀和定义，再说「等值前缀和 ↔ 零和区间」这句等价话，代码就水到渠成。主动提「和为 k」的推广，以及为什么不能滑动窗口（负数让窗口和失去单调性，见 033 章）。

思路（先问口径！）。这道题的精髓在澄清：「任意子数组」是否允许长度 1？是否要求长度至少为某个 \(k\)？若长度不受限，答案是最大单元素——因为任何子数组的平均数不超过其最大元素（加权平均不超过最大值），而单元素子数组恰好取到最大元素本身，所以答案就是 \(\max_i a_i\)。这是面试官设的陷阱：很多人条件反射地写 Kadane 或对「平均值」做窗口，方向就错了。若要求长度至少为 \(k\)，则用二分答案：判定「是否存在长度 ≥ k、平均值 ≥ x 的子数组」，把每个元素减去 \(x\) 后，问题变成「是否存在长度 ≥ k、和 ≥ 0 的子数组」，用前缀和与前缀最小值一遍判定；答案对值域二分到给定精度。

代码（不受限版）。

double maxAverage(const vector<int>& a) {     // 不限长度：答案就是最大单元素
    return *max_element(a.begin(), a.end());
}

代码（长度至少为 k 版）。

double maxAverageAtLeastK(const vector<int>& a, int k) {  // 长度 >= k 的最大均值
    double lo = *min_element(a.begin(), a.end());
    double hi = *max_element(a.begin(), a.end());
    auto ok = [&](double x) {                 // 是否存在长度 >= k 且均值 >= x 的子数组
        vector<double> P(1, 0.0);              // P：每个元素减 x 后的前缀和
        for (int v : a) P.push_back(P.back() + v - x);
        double preMin = 0.0;
        for (size_t i = k; i < P.size(); ++i) {
            preMin = min(preMin, P[i - k]);    // 维护 min P[0..i-k]，与 P[i] 恰好拉开 k
            if (P[i] - preMin >= 0) return true;
        }
        return false;
    };
    while (hi - lo > 1e-6) {                   // 值域二分到精度即可
        double mid = (lo + hi) / 2;
        (ok(mid) ? lo : hi) = mid;
    }
    return lo;
}

复杂度。不受限版 \(O(n)\) 且几乎零成本；至少 k 版每次判定 \(O(n)\)，共 \(O\bigl(n \log\frac{V}{\varepsilon}\bigr)\)，\(V\) 为值域宽度、\(\varepsilon\) 为精度。

边界。空数组非法；\(k = 1\) 退化为不受限版；均值是浮点数，比较用容差而非严格相等；二分的循环条件用区间宽度控制而不是固定次数时，注意精度的十进制位与题面要求对齐。

面试怎么讲。第一句话应当是反问：「子数组长度有下限吗？」然后分两个口径作答。把「平均值不超过最大元素」这步不等式说清楚，是这道题的得分点；直接报出「不限长度就是 max」往往正是面试官想听的信号。