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!
Select
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
Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
play-icon
play-icon
qr-code
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

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2025 Info Edge (India) Ltd.

Follow Us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
AmbitionBox Employee Choice Awards 2025
Winners announced!
awards-icon
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits