SQLKADANE - Editorial

editorial
1

PROBLEM LINK:

Practice
Contest:

DIFFICULTY:

TBD

PREREQUISITES:

Case, Union All, Recursive SQL, Kadane’s Algorithm

PROBLEM:

Your task is to output the maximum subarray sum of an array.

EXPLANATION:

This solution uses Recursive SQL.

We translate the usual Kadane’s algorithm to Recursive SQL:

We construct a new table with 3 columns - key, value, and MaxEnding.
MaxEnding[i] is defined to be the max sum subarray which ends at A[i].

We build this table using Recursive SQL, and using CASE to do the if/else conditional of whether or not we want to include the previous MaxEnding in the current sum.

And remember to have the column alias set correctly.

Code 
WITH R AS (
    SELECT key1 AS k, val1 as v,
    CASE WHEN ArrayTable.val1 >= 0 THEN ArrayTable.val1
    ELSE 0
    END AS MaxEnding
    FROM ArrayTable
    WHERE key1 = 1
    
    UNION ALL
    
    SELECT k+1,ArrayTable.val1,
    CASE WHEN MaxEnding >= 0 THEN MaxEnding + ArrayTable.val1
    ELSE ArrayTable.val1
    END AS MaxEnding
    FROM R, ArrayTable WHERE ArrayTable.key1 = k+1
    )

SELECT MAX(MaxEnding) AS 'Max Subarray Sum' FROM R
1 Like