Maximum Sum Subarray - SQL

---

🛠️ Problem Statement

I found this problem on Codechef.

Given an array A = [A[1], A[2], ..., A[N]] you need to find the maximum sum among all its subarrays.

Note that a subarray is any contiguous set of elements of the array.

However, the array is given to you as a database table:

You have a table ArrayTable, with 2 columns, as follows:

Table Name : ArrayTable

Column Name	Type
key1	int
val1	int

• key1 corresponds to the index, and val1 corresponds to the value. That is, A[key1]=val1
• It is guaranteed that if there are a total of N rows in the table, then all the key1s are exactly {1,2,…,N}.

Write a SQL query to find the maximum sum among all its subarrays.

The query result format is in the following example:

Input

Table Name : ArrayTable

key1	val1
1	10
2	-40
3	20
4	35
5	-2

Output

Max Subarray Sum
55

---