问题的回答。

问题的历史。

Kadane 的算法，由 Jay Kadane 在 1984 年提出，通过动态编程解决最大子数组问题，跟踪两个状态：当前职位的最大和以及遇到的全局最大值。将这种命令式模式转化为声明式的 ANSI SQL 需要通过 递归 CTE 模拟顺序迭代，因为标准窗口函数无法以相互递归的方式表达依赖于先前行计算结果的运行聚合。这个问题测试候选人在基于集合处理的约束下实现复杂算法逻辑的能力。

问题。

给定一个有序数字观察值的表格（例如，每日利润/损失），目标是识别出产生最高可能和的单个连续行块。与简单的运行总和不同，最优子数组可以在任意点开始和结束，而决定是否在每行扩展当前子数组或重新开始依赖于立即前面的子数组的累积和——这种依赖关系创造了一个递归定义，禁止简单聚合。

解决方案。

我们利用 递归 CTE，以初始行的值作为 current_max_ending_here 和 global_max_so_far 进行初始化。递归成员通过一个排序键连接到后续行，计算新的 current_max 为 GREATEST(current_value, previous_current_max + current_value)，并将 global_max 更新为 GREATEST(previous_global_max, new_current_max)。最终聚合选择所有迭代中最大的 global_max。这种方法以每个分区的 O(n) 时间执行，同时保持严格的基于集合的处理。

WITH RECURSIVE numbered AS (
    SELECT 
        partition_id,
        observation_date,
        value,
        ROW_NUMBER() OVER (PARTITION BY partition_id ORDER BY observation_date) AS rn
    FROM daily_returns
),
kadane AS (
    -- 锚点：用每个分区的第一行初始化
    SELECT 
        partition_id,
        rn,
        value,
        value AS current_max_ending_here,
        value AS global_max_so_far
    FROM numbered
    WHERE rn = 1
    
    UNION ALL
    
    -- 递归步骤：向前传播状态
    SELECT 
        n.partition_id,
        n.rn,
        n.value,
        GREATEST(n.value, k.current_max_ending_here + n.value) AS current_max_ending_here,
        GREATEST(k.global_max_so_far, GREATEST(n.value, k.current_max_ending_here + n.value)) AS global_max_so_far
    FROM kadane k
    JOIN numbered n 
        ON k.partition_id = n.partition_id 
        AND n.rn = k.rn + 1
)
SELECT partition_id, MAX(global_max_so_far) AS maximum_subarray_sum
FROM kadane
GROUP BY partition_id;

生活中的情况

一个定量交易桌需要识别出动量策略的最佳历史窗口——具体而言，产生最高累计回报的连续交易日序列，针对每个资产类别。数据集中包含数百万个按股票符号分区的每日 P&L 记录，研究团队需要对成千上万的证券进行亚秒延迟的临时分析。

最初的概念验证使用了一种“暴力”自连接方法，将表与自身交叉连接，以生成所有可能的开始和结束日期，然后汇总它们之间的和。虽然这不需要 递归 CTE，而且易于构思，但其 O(n²) 的复杂性导致查询超时，经过数小时的执行，使其无法在生产规模分析中使用，因为 CPU 和 I/O 的消耗过大。

另一种替代方法在 Python 中使用 psycopg2 利用过程游标迭代行，同时保持运行变量。这提供了直观的命令式逻辑和便于调试的能力，但违反了团队在数据库内部计算的要求，以最小化数据传输开销，基于游标的处理由于往返延迟和缺乏基于集合的优化表现不佳。

递归 CTE 实现模拟 Kadane 的算法 被选中。该解决方案对每个分区进行一次线性处理，仅在每个递归级别存储两个标量值，并利用数据库引擎对递归查询的本机优化。它在整个数据集上实现了所需的毫秒级响应时间，同时保持纯声明式。

该实现成功识别出超过五千个证券的最大盈利串，在 400 毫秒内完成。随后，DBA 团队采纳了这一模式用于类似的“最佳窗口”分析，包括风险指标计算和波动率聚类检测。

候选人常常遗漏的内容

递归 CTE 如何处理仅包含负值的分区，以及为何初始锚行选择防止错误返回零？

许多候选人在锚成员中错误地将 current_max 和 global_max 初始化为零，这会导致算法对全负序列返回零（错误暗示一个空子数组是最优的）。正确的做法是将两个聚合初始化为每个分区内第一行的实际值。这确保对于像 [-5, -2, -8] 的序列，查询正确返回 -2 而不是 0，遵循子数组必须至少包含一个元素的约束。未能考虑这一边缘情况会导致在分析仅损失的期间时发生静默逻辑错误。

您可以仅使用严格的 ANSI SQL 来检索最大子数组的实际起始和结束边界（特定行），而不仅仅是和值吗？

可以，但需要扩展递归 CTE 来跟踪元数据。您必须传递两个额外的列：current_start_rn（当前候选子数组的起始索引）和 best_start_rn/best_end_rn（全局最大值的边界）。在递归成员中，如果当前值单独超过扩展的和，则将 current_start_rn 设置为当前 row_num；否则，从前一行继承。当 global_max_so_far 更新时，捕获当前 row_num 作为 best_end_rn 和 current_start_rn 作为 best_start_rn。这表明理解 递归 CTE 可以维护复杂的状态对象，而不仅仅是标量累加器，从而允许重建最优窗口的位置。

为什么无法使用标准窗口函数，比如 SUM() OVER 或 MAX() OVER 来解决这个问题，SQL 标准的哪些具体限制妨碍了基于窗口的方法？

标准窗口函数在静态定义的框架上计算聚合（例如 ROWS BETWEEN）。最大子数组问题需要一个运行聚合，其中是否包含当前行取决于前一行的聚合结果——具体来说，那个前一和是否为正。这创建了一个相互依赖或递归的情况，窗口函数无法表达，因为它们缺乏从同一结果集中的前一行引用窗口函数输出的能力。递归 CTE 是必需的，因为它们允许一轮的输出作为下一轮的输入，有效地实现在声明式范式中的逐行状态计算。

当被挑战从有序分区中隔离出连续行的子序列，以产生最大的累积值——模拟 Kadane 的算法——您将如何使用严格的 ANSI SQL 递归 CTE 来计算这个最大子数组和，而不使用过程迭代？

问题的回答。

生活中的情况

候选人常常遗漏的内容