GSS1  Can you answer these queries I
You are given a sequence A[1], A[2], ..., A[N] . ( A[i] ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:
Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.
Given M queries, your program must output the results of these queries.
Input
 The first line of the input file contains the integer N.
 In the second line, N numbers follow.
 The third line contains the integer M.
 M lines follow, where line i contains 2 numbers xi and yi.
Output
Your program should output the results of the M queries, one query per line.
Example
Input: 3 1 2 3 1 1 2 Output: 2
hide comments
huangdachuan:
20210821 23:37:58
See Finding subsegments with the maximal sum in the https://cpalgorithms.com/data_structures/segment_tree.html the key is to understand the recursive query logic. 

matinzare:
20210724 10:10:55
15007 × 50000 = 750350000 = > int


Waseem Ahmed:
20210717 20:02:41
Finally solved it using Segment Trees.


hello_baby:
20210622 00:29:18
First solve the "maximum sum subarray" or "longest contiguous subarray sum" using divide and conquer, you can easily solve this. 

ive1010:
20210620 19:39:52
Small hint: need to store more than 1 information in Segment Tree 

tropo_sphere:
20210612 17:14:12
size of M?


loser_404:
20210609 05:40:25
check this lecture from paska(cfedu)


rimuru_404:
20210605 11:39:18
Finally AC :) . Good question... 

csd_123:
20210525 14:01:23
can it be solved using kadane's algorithm for each query 

gupta_suraj143:
20210514 14:53:25
can anyone provide me some extra test cases

Added by:  Nguyen Dinh Tu 
Date:  20061101 
Time limit:  1s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 