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