Ответ на вопрос.

История вопроса.

Алгоритм Кадане, сформулированный Джеем Кадане в 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²) сложность привела к тайм-аутам запросов после часов выполнения, что делало его непрактичным для производственного анализа из-за чрезмерного потребления ЦП и I/O.

Альтернативный подход использовал процедурный курсор в Python с psycopg2, чтобы перебирать строки, сохраняя текущие переменные. Это предлагало интуитивно понятную императивную логику и простоту отладки, но нарушало мандат команды на вычисления в базе данных, чтобы минимизировать накладные расходы на передачу данных, а обработка на основе курсоров демонстрировала плохую производительность из-за задержек при обратных вызовах и отсутствия оптимизации в наборной обработке.

Имплементация рекурсивного CTE, имитирующая алгоритм Кадане, была выбрана. Это решение обрабатывало каждый раздел за единственный линейный проход, храня только два скалярных значения на каждом уровне рекурсии и используя родную оптимизацию движка базы данных для рекурсивных запросов. Оно достигло желаемого времени отклика на уровне миллисекунд по всему набору данных, оставаясь чисто декларативным.

Реализация успешно определила максимальные прибыльные последовательности для более чем пяти тысяч ценных бумаг за 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 необходимы, потому что они позволяют выходу одной итерации служить входом для следующей, эффективно позволяя вычислению состояния по строкам внутри декларативной парадигмы.