Antwoord op de vraag.

Geschiedenis van de vraag.

Kadane's Algoritme, geformuleerd door Jay Kadane in 1984, lost het maximale subarray probleem op via dynamische programmering door twee toestanden bij te houden: de maximale som die eindigt op de huidige positie en de globale maximum die is tegengekomen. Het vertalen van dit imperatieve patroon naar declaratieve ANSI SQL vereist het simuleren van sequentiële iteratie via Recursieve CTE's, aangezien standaard vensterfuncties geen lopende aggregaten kunnen uitdrukken die afhankelijk zijn van eerder berekende resultaten van rijen op een wederzijds recursieve manier. Dit probleem test het vermogen van een kandidaat om complexe algoritmische logica te implementeren binnen de beperkingen van set-gebaseerde verwerking.

Het probleem.

Gegeven een tabel met geordende numerieke observaties (bijv. dagelijkse winst/verlies), is het doel om het enkele aaneengeschakelde blok van rijen te identificeren dat de hoogste mogelijke som produceert. In tegenstelling tot een eenvoudige lopende totalen kan de optimale subarray beginnen en eindigen op willekeurige punten, en de beslissing om de huidige subarray uit te breiden of opnieuw te beginnen bij elke rij hangt af van de cumulatieve som van de onmiddellijk voorafgaande subarray—een afhankelijkheid die een recursieve definitie creëert die eenvoudige aggregatie verbiedt.

De oplossing.

We maken gebruik van een Recursieve CTE die de initiële rij zaait met zijn waarde als zowel current_max_ending_here als global_max_so_far. Het recursieve lid voegt zich samen met de volgende rij met behulp van een sorteersleutel, waarbij de nieuwe current_max wordt berekend als GREATEST(current_value, previous_current_max + current_value) en global_max wordt bijgewerkt als GREATEST(previous_global_max, new_current_max). Een laatste aggregatie selecteert de maximale global_max over alle iteraties. Deze aanpak voert uit in O(n) tijd per partitie, terwijl het strikt set-gebaseerd blijft.

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 (
    -- Anker: initialiseren met de eerste rij van elke partitie
    SELECT 
        partition_id,
        rn,
        value,
        value AS current_max_ending_here,
        value AS global_max_so_far
    FROM numbered
    WHERE rn = 1
    
    UNION ALL
    
    -- Recursieve stap: propageren van de status naar voren
    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;

Situatie uit het leven

Een kwantitatieve handelsdesk moest het optimale historische venster voor een momentumstrategie identificeren—specifiek, de aaneengeschakelde reeks handelsdagen die de hoogste cumulatieve opbrengst opleverde voor elke activaklasse. De dataset bevatte miljoenen dagelijkse P&L-registraties verdeeld per aandelensymbool, en het onderzoeksteam vereiste sub-seconde latentie voor ad-hoc analyses over duizenden effecten.

Het initiële bewijs van concept gebruikte een brute-force zelf-join benadering die de tabel met zichzelf kruiste om alle mogelijke start- en einddata te genereren, en vervolgens aggregaten tussen hen berekende. Hoewel dit geen Recursieve CTE vereiste en eenvoudig te conceptualiseren was, leidde de O(n²) complexiteit tot query timeouts na uren van uitvoering, waardoor het niet levensvatbaar was voor productieanalyse vanwege overmatige CPU en I/O consumptie.

Een alternatieve aanpak gebruikte een procedurele cursor in Python met psycopg2 om rijen te itereren terwijl lopende variabelen werden onderhouden. Dit bood intuïtieve imperatieve logica en eenvoudige debugging, maar schond het mandaat van de team voor in-database berekeningen om gegevensoverdracht overhead te minimaliseren, en cursor-gebaseerde verwerking vertoonde een slechte prestaties door round-trip latentie en gebrek aan set-gebaseerde optimalisatie.

De Recursieve CTE implementatie die Kadane's Algoritme simuleerde werd gekozen. Deze oplossing verwerkte elke partitie in een enkele lineaire pas, die slechts twee scalare waarden per recursieniveau opsloeg en de optimale prestaties van de database-engine voor recursieve queries benutte. Het bereikte de gewenste milliseconde-reactietijden over de gehele dataset terwijl het puur declaratief bleef.

De implementatie identificeerde met succes de maximale winstgevende reeksen voor meer dan vijfduizend effecten binnen 400 ms. Het DBA-team nam deze patroon vervolgens over voor vergelijkbare "beste venster" analyses, inclusief risico-metrieken en volatiliteitsclusteringdetectie.

Wat kandidaten vaak missen

Hoe gaat de recursieve CTE om met partities die uitsluitend negatieve waarden bevatten, en waarom voorkomt de initiële ankerrijselectie de foutieve terugkeer van nul?

Veel kandidaten initialiseren current_max en global_max verkeerdelijk op nul in het ankerlid, wat ertoe leidt dat het algoritme nul retourneert voor geheel negatieve reeksen (onterecht implicerend dat een lege subarray optimaal is). De correcte aanpak initialiseert beide aggregaten op de werkelijke waarde van de eerste rij binnen elke partitie. Dit zorgt ervoor dat voor een reeks als [-5, -2, -8], de query correct -2 retourneert in plaats van 0, in overeenstemming met de beperking dat de subarray ten minste één element moet bevatten. Het niet rekening houden met deze randgeval resulteert in stille logische fouten bij het analyseren van verlies-only periodes.

Kun je de werkelijke start- en eindgrenzen (de specifieke rijen) van de maximale subarray ophalen, niet alleen de somwaarde, met uitsluitend ANSI SQL?

Ja, maar het vereist het uitbreiden van de recursieve CTE om metadata bij te houden. Je moet twee extra kolommen doorgeven: current_start_rn (de startindex van de huidige kandidaat subarray) en best_start_rn/best_end_rn (de grenzen van het globale maximum). In het recursieve lid, als de huidige waarde alleen de uitgebreide som overschrijdt, stel dan current_start_rn in op de huidige row_num; anders, erf het van de vorige rij. Wanneer global_max_so_far wordt bijgewerkt, vastleggen de huidige row_num als best_end_rn en current_start_rn als best_start_rn. Dit toont aan dat Recursieve CTE's complexe state-objecten kunnen behouden, niet alleen scalare accumulators, waardoor reconstructie van de locatie van het optimale venster mogelijk is.

Waarom kan dit probleem niet worden opgelost met standaard vensterfuncties zoals SUM() OVER of MAX() OVER, en welke specifieke beperking van de SQL-standaard voorkomt een venster-gebaseerde aanpak?

Standaard vensterfuncties berekenen aggregaten over statisch gedefinieerde frames (bijv. ROWS BETWEEN). Het maximale subarray-probleem vereist een lopende aggregaat waarbij de beslissing om de huidige rij op te nemen afhankelijk is van de resultaat van de aggregatie voor de vorige rij—specifiek, of die vorige som positief was. Dit creëert een wederzijdse afhankelijkheid of recursie die vensterfuncties niet kunnen uitdrukken omdat ze niet in staat zijn om de uitvoer van de vensterfunctie van de onmiddellijk voorafgaande rij in dezelfde resultaten set te refereren. Recursieve CTE's zijn vereist omdat ze de uitvoer van de ene iteratie als invoer voor de volgende kunnen gebruiken, waardoor rij-voor-rij statusvolle berekening binnen het declaratieve paradigma mogelijk wordt.