0

Maximum Subarray Sum Queries

Difficulty: HARD
Contributed By
Ankit Kharb
Avg. time to solve
45 min
Success Rate
55%

Problem Statement

Given an array of ‘N’ integers and ‘Q’ queries. The query is defined as below :-

Given 2 integers ‘l’ and ‘r’ (‘l’ >= 0 and ‘r’ < N) find the maximum subarray sum between ‘l’ to ‘r’ (Inclusive).

Query( ‘l’ ,’r’) = max(arr[i] + arr[i+1] +...arr[j].( i >= ‘l’ and j <= ‘r’)

Input Format :

The first line contains ‘T,’ denoting the number of test cases.

The first line of the test case contains a single integer ‘N’  denoting the size of the ‘arr’ array.

The second line of each test case contains ‘N’ space-separated integers denoting the array ‘arr’.

The third line of each test case contains an integer ‘Q’ denoting the number of queries.

The next ‘Q'  lines of each test case contain 2 space-separated integers denoting the following:

The first integer denotes ‘l’ and the second integer denotes ‘r’  which are the range for which we need to calculate max(arr[i] + arr[i+1] +...arr[j].( i >= ‘l’ and j <= ‘r’).

Output Format :

For each query print an integer denoting the maximum possible value.in the range of ‘l’ and ‘r’.

The output for each test case will be printed in a separate line.

Note :

You need not to print anything. It has been already taken care of. Just implement the function.

Constraints :

 1 <= T <= 5
 1 <= N <= 10^5
 1 <= Q <= 10^5
 -10^9 <= arr[i] <= 10^9

Where ‘arr[i]’ is the value of the element at index ‘i’.

Time Limit: 1 sec

Sample Input 1 :

1
5
1 2 3 4 -5
3
0 2
1 3
0 4
Sample Output 1 :
6
9
10
Explanation for sample output 1 :
The first line has a single integer which means it’s a single test case.
The next line has an integer 5 denoting that there are 5 integers in the array.
Then the 5 space-separated integers in the third line represent the elements in the array.
Then the fourth line has ‘Q’ which is the number of queries. In this case, we have 3 queries.

The 3 queries are as follow:-
In first query ‘l’ = 0 and ‘r’ = 2
Thus maximum possible value is arr[0] + arr[1] + arr[2] = 1 + 2 + 3 = 6

In second query ‘l’ = 1 and ‘r’ = 3
Thus maximum possible value is arr[1] + arr[2] + arr[3] =  2 + 3 +4 = 9

 In third query ‘l’ = 0 and ‘r’ = 4
Thus maximum possible value is arr[0] + arr[1] + arr[2] + arr[3] = 1+  2 + 3 +4 = 10
Sample Input 2 :
2
3
-10 -19 -13 
3
0 2
1 2
1 1
5
6 4 0 -17 -19 
1
0 2
Sample Output 2 :
-10
-13
-19
 10
Reset Code
Full screen
copy-code
Console