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.
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.
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.
nums.lengthqueries.length ≤5⋅104nums[i] ≤15000[l, r] in queries