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’ = ‘l’ and j = ‘l’ and j

Question

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

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1)

We are using constant space to solve this.

Time Complexity: O(n^2)Explanation:

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

Python (3.5)

"""

   Time Complexity : O(N * Q)

   Space Complexity : O(1)



   where N is size of array and Q is number of queries.



"""





def kadane(arr, l, r):



    ans = -999999999

    summ = 0

    for i in range(l, r+1):



        summ += arr[i]

        ans = max(ans, summ)

        if (summ < 0):



            summ = 0



    return ans





def solve(n, arr, q, queries):

    

    ans1 = []

    for i in range(q):



        # Kadane will find max_subarray summ witihin given range.

        ans = kadane(arr, queries[i][0], queries[i][1])

        ans1.append(ans)



    return ans1

C++ (g++ 5.4)

/*

   Time Complexity : O(N * Q)

   Space Complexity : O(1)



   where N is size of array and Q is number of queries.

*/



#include



int kadane(vector &arr, int l, int r)

{

	int ans = INT_MIN;

	int sum = 0;

	for (int i = l; i <= r; i++)

	{

		sum += arr[i];

		ans = max(ans, sum);

		if (sum < 0)

		{

			sum = 0;

		}

	}

	return ans;

}



vector solve(int n, vector &arr, int q, vector> &queries)

{

	vectorans1;

	for (int i = 0; i < q; i++)

	{

		// Kadane will find max_subarray sum witihin given range.

		int ans = kadane(arr, queries[i][0], queries[i][1]);

		ans1.push_back(ans);

	}

	return ans1;

}

Java (SE 1.8)

/*

   Time Complexity : O(N * Q)

   Space Complexity : O(1)



   where N is size of array and Q is number of queries.

*/



public class Solution 

{

    public static int kadane(int[] arr, int l, int r)

    {

	    int ans = Integer.MIN_VALUE;

	    int sum = 0;



	    for (int i = l; i <= r; i++)

	    {

		    sum += arr[i];

		    ans = Math.max(ans, sum);

 		    if (sum < 0)

		    {

			   sum = 0;

		    }

	    }

	    return ans;

    }



    public static int[] solve(int n, int[] arr, int q, int[][] queries)

    {

    	int[] ans1 = new int[q];

	    for (int i = 0; i < q; i++)

	    {

		   // Kadane will find max_subarray sum witihin given range.

		   int ans = kadane(arr, queries[i][0], queries[i][1]);

		   ans1[i] = ans;

	    }

	

        return ans1;

    }

}

Accepted Answer

Segment Tree Approach

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.

Space Complexity: O(n)Explanation:

O(N) where N is the size of given array.

We are creating an array of size 4* N + 1 . Thus space complexity will be O(N).

Time Complexity: O(nlogn)Explanation:

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

We have to build segment tree which takes N*log(N) and we have to process Q queries and each query takes log(N) time with the segment tree .