PROBLEM LINK:
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