Maximum Subarray Sum Queries

Hard

0/120

Average time to solve is 45m

Contributed by

7 upvotes

Asked in companies

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’)

Detailed explanation ( Input/output format, Notes, Images )

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 :

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 :

Hint 1

Hint 2

Use the Kadane algorithm.

Approaches (2)

Approach 1

Approach 2

Brute Force Approach

The key idea is to process the queries as asked. Forgiven ‘l’ and ‘r’ we need to find the maximum sub-array sum from ‘l’ to ‘r’. For this, we can use the Kadane algorithm. To know more about the Kadane algorithm refer to this:-

https://cp-algorithms.com/others/maximum_average_segment.html

Time Complexity

O(N * Q) where ‘N’ is the size of array and ‘Q’ are the number of queries.

In the worse case, we need to find subarray sum from 0 to N - 1 Q times. The time complexity of Kadane is O(N) hence the worse case complexity will be O(N * Q).

Space Complexity

O(1)

We are using constant space to solve this.

(100% EXP penalty)

Maximum Subarray Sum Queries

Console