Maximum Subarray Sum Queries
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
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
The main idea is to process the queries efficiently we will use a segment tree.To know more about segment tree refer this :- https://cp-algorithms.com/data_structures/segment_tree.html
At each node in the segment tree we will store 4 values:-
Sum:- The sum of all numbers in the subsegment which a particular node denotes to.
Max_Sum:- We will store the maximum possible sub-array sum of a particular segment.
Max_Prefix_Sum:- This denotes the maximum prefix sum of the segment.
Max_Suffix_Sum:- This denotes the maximum suffix sum of the segment.
Using these four values we can get the answer query for any segment.
Now to combine the answer from two child nodes we have to do the following:-
The Sum for the parent node will be:-
parent.Sum = leftChild.sum + rightChild.sum
parent.Max_Sum = max( leftChild.Max_Sum , rightChild.Max_Sum , leftChild.MaxSuffix_Sum + rightChild.MaxPreffix_Sum)
The reason for this is:-
The Max_sum for a parent can be is maximum of leftChild.Max_Sum and rightChild.Max_Sum and sum of Suffix_Sum of left and Preffix_Sum of right.
Max_Suffix of a parent is maximum of right child Suffix_Sum and left Child SuffixSum plus sum of rightChild.
Max_Prefix of the parent is maximum of left child Preffix_Sum and right Child PreffixSum plus the sum of left child.