"Can you answer this queries" problem from SPOJ?

I was solving GSS1 - Can you answer these queries I problem from SPOJ, but I have one query in statement Max { a[i]+a[i+1]+…+a[j] ; x ≤ i ≤ j ≤ y }, does this mean we have to find max sum subarray with in the given range.

Please explain approach to solve this problems in details.

Yes, it means to find the max sum subarray within given range.

Approach: Range queries, So, Segment tree should be the first DS that comes to mind. What should a node hold in segment tree such that we will not miss any corner cases? Think about the possible cases which can generate answers. Cleary, optimal subarray could be like [l,i] or could be [i,R] or [i,j], where l<=i <=j<=R.

[l, i] may suggest some sort of prefix.

[i, R] suggest some suffix

Also, in segment tree building process depends on just child nodes. So, how can you cover all cases ?? Think in this manner.

@vikram91 @rs_710 @purendra_ @hemanth_1 @shraeyas @vidyut_1 @aryanc403 @meooow @alexthelemon @vijju123 @ram_24 @harrypotter0 @pankaj_chopra guys please help.

@gagan86nagpal

Can you please tell me in more details.

Check out my implementation and feel free to ask anything

Create a segment tree,node representing [i,j] lets call node p ,contains max subarray sum(Ap),max prefix sum(Pp),max suffix sum(Sp),totalSum(Tp)

Lets say node p in seg has child q(left child),r

So Ap=max(Aq,Ar,Sq+Pp)

Pp=max(Pq,Tq+Pr)

Sp=max(Sr,Tr+Sq)

Tp=Tq+Tr

Using this construct seg

3 Likes

And yeah,learn to upvote some1 if u think they solved ur doubts,people like me would help as we like to help,bt some people help to get some karma,and i really have never seen u upvote some1,so better do if they solve ur doubts,else people wont help u again :slight_smile:

1 Like

@vivek_1998299

People were less active in answering my doubts, I think this was the reason. Thank you so much vivek for helping me and opening my eyes as well.
Thank you so much

Can you please look into this, I am getting TLE.
https://discuss.codechef.com/questions/126183/editorial-request-for-sereja-and-brackets-from-codeforces

@vivek_19982995

Can you please explain in more details.

https://discuss.codechef.com/questions/96902/spoj-gss1-problem

Check this out,i dont think i can explain better than them.

1 Like

@vivek_1998299
I solved using approach described there, but I am getting TLE. I have spent too much time on it. Please help.

Thanks in advance