SPOJ.com - Problem GSS1

GSS1 - Can you answer these queries I

#tree

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

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 10 11 Next >

	Phi: 2022-08-15 14:01:47 I'm not sure I understand the query definition? Are we looking for a sum of a[i] up to a[j]? If yes, why do we need max{} then (it would be a max from a single value)? Or are we interested in a max over a[i] up to a[j]? If yes, why are there pluses between a[i]s? Last edit: 2022-08-15 14:01:59
	vikash_singh18: 2022-07-04 12:41:13 tumse na ho payega
	onlyerror: 2022-06-29 13:46:22 For those who are getting a wrong answer return -1000000 for invalid ranges
	amank12345: 2022-06-12 20:20:32 I have been trying it through java,but worst part is that,this platform unlike leetcode doesn't show the test case where the code failed. this is just worst platform. it doesn't even show the testcases ,no option of initial run. can't even figure out whats the problem.
	two_plus_three: 2022-06-10 09:34:39 Can someone please provide me a testcase at which this solution fails? <snip> [Simes]: Please use the forum for this. Last edit: 2022-06-10 10:13:03
	huangdachuan: 2021-08-21 23:37:58 See Finding subsegments with the maximal sum in the https://cp-algorithms.com/data_structures/segment_tree.html the key is to understand the recursive query logic.
	matinzare: 2021-07-24 10:10:55 15007 × 50000 = 750350000 = > int but after WA on 9 and change it to long long got AC :/
	Waseem Ahmed: 2021-07-17 20:02:41 Finally solved it using Segment Trees. Advice : While this is a standard problem and tutorials and codes are available online, solve it yourself for a wonderful learning experience on segment trees. And thanks a lot to all the users who provided the sample test cases.
	hello_baby: 2021-06-22 00:29:18 First solve the "maximum sum subarray" or "longest contiguous subarray sum" using divide and conquer, you can easily solve this.
	ive1010: 2021-06-20 19:39:52 Small hint: need to store more than 1 information in Segment Tree

Submit solution!

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