
Asked in Freshworks
Maximum Subarray Sum Queries
You are provided with an array of ‘N’ integers and ‘Q’ queries. Each query requires calculating the maximum subarray sum in a specified range of the array.
Input:
The first line contains ‘T’, representing the number of test cases. Each test case comprises the following: - The first line contains a single integer ‘N’ denoting the size of the ‘arr’ array. - The second line contains ‘N’ space-separated integers that represent the array ‘arr’. - The third line contains an integer ‘Q’ denoting the number of queries. - The next ‘Q’ lines in each test case contain two space-separated integers: ‘l’ and ‘r’, representing the range for which you must calculate the maximum subarray sum.
Output:
For each query per test case, output an integer denoting the maximum possible subarray sum in the range ‘l’ to ‘r’. Each test case should produce outputs on separate lines.
Example:
For a single test case, consider:
Input:
N = 5
arr = [-2, 1, -3, 4, -1]
Q = 2
Query 1: l = 0, r = 4
Query 2: l = 1, r = 3
Output:
4
2
Explanation: For the first query, the maximum subarray sum between indices 0 and 4 is 4 (subarray [4]). For the second query, the maximum subarray sum between indices 1 and 3 is 2 (subarray [1, -3, 4]).
Constraints:
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 105
- 1 ≤ Q ≤ 105
- -109 ≤ arr[i] ≤ 109
Ensure your solution meets the time limitation of 1 second.
Note:
Note that you do not need to print the output yourself. Implement the function as instructed and the results will be handled accordingly.

AnswerBot
4mo
Implement a function to calculate maximum subarray sum queries in a given range of an array.
Iterate through each query and calculate the maximum subarray sum within the specified range using Kadane's ...read more
Help your peers!
Add answer anonymously...
Top Software Developer Interview Questions Asked at Freshworks
Q. Wildcard Pattern Matching Problem Statement Implement a wildcard pattern matchin...read more
Q. What is a deadlock in DBMS, and can you explain the concepts of join and query?
Q. Sort 0 1 2 Problem Statement Given an integer array arr of size 'N' containing o...read more
Interview Questions Asked to Software Developer at Other Companies
Top Skill-Based Questions for Freshworks Software Developer
Algorithms Interview Questions and Answers
250 Questions
Data Structures Interview Questions and Answers
250 Questions
Web Development Interview Questions and Answers
250 Questions
Java Interview Questions and Answers
250 Questions
SQL Interview Questions and Answers
250 Questions
Software Development Interview Questions and Answers
250 Questions
Stay ahead in your career. Get AmbitionBox app


Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+
Reviews
10L+
Interviews
4 Cr+
Salaries
1.5 Cr+
Users
Contribute to help millions
AmbitionBox Awards
Get AmbitionBox app

