Maximum Subarray Sum Queries

You are given an integer array nums and a list queries. Each element in queries contains [l, r] meaning the query looks only at nums[l..r], the part of nums from index l to index r, both included.

The answer to a query is the largest sum of a contiguous subarray that lies entirely inside nums[l..r]. The subarray must contain at least one element, so a range of only negative values has a negative answer.

Return a list with the answer to each query, in the same order as queries.

Examples

Example 1

Input: nums = [2,-3,4,-1,2,-5,3], queries = [[0,6],[0,1],[3,5],[5,5]]
Output: [5,2,2,-5]
Explanation: Over the whole array the best subarray is [4,-1,2] with sum 5.
In nums[0..1] = [2,-3] the best choice is [2] alone.
In nums[3..5] = [-1,2,-5] the best choice is [2] alone.
nums[5..5] = [-5] has only one subarray, so the answer is -5.

Example 2

Input: nums = [-4,-2,-7], queries = [[0,2],[2,2]]
Output: [-2,-7]
Explanation: Every value is negative, so the best subarray of a range is its largest single value.
The largest value in nums[0..2] is -2, and nums[2..2] holds only -7.

Example 3

Input: nums = [5,-9,6], queries = [[0,2],[0,1],[1,2]]
Output: [6,5,6]
Explanation: In nums[0..2] the whole range sums to 2, but [6] alone gives 6.
In nums[0..1] the best choice is [5], and in nums[1..2] it is [6].