Maximum Subarray Sum and Queries
Time limit2sMemory limit512 MB
Given an array, answer queries that ask for the maximum subarray sum inside a given index range.
- Level
Hard8 of 10
- Topics
- Segment tree, Divide and conquer, Dynamic programming, Array
- Solved
- No attempts yet
Problem
You are given a sequence A1, A2, ..., AN of length N. Write a program that processes the following queries.
i j: Output the maximum subarray sum within Ai, Ai+1, ..., Aj. (1 ≤ i ≤ j ≤ N)
The indices of the sequence start at 1.
The subarray sum is the largest sum obtainable by selecting several consecutive numbers, and at least one number must be selected.
Input
The first line gives the size of the sequence, N. (1 ≤ N ≤ 100,000)
The second line gives A1, A2, ..., AN. (-1,000 ≤ Ai ≤ 1,000)
The third line gives the number of queries, M. (1 ≤ M ≤ 100,000)
Each of the following M lines gives a query.
Output
Print the answer to each query, one per line, in order.