### rb9's blog

By rb9, 5 years ago, ,

I was trying to solve this problem http://www.spoj.com/problems/GSS1/, after sometime I gave up and googled approach for it, I found this website https://kartikkukreja.wordpress.com/2014/11/09/a-simple-approach-to-segment-trees/ but still not able to understand problem and its solution.Plz help!

• -5

 » 5 years ago, # | ← Rev. 2 →   +8 I will explain my approach and I will give you my code.In this problem we need to keep a structure in each node that can help us to determine the answer for a node from its children. The structure that I used is the following: struct Node { int sum_left,sum_right,sum_max,sum_total; bool indicator; }; sum_left — the maximum sum of consecutive elements that contains the leftmost element in the range.sum_right — the maximum sum of consecutive elements that contains the rightmost element in the range.sum_max — the answer for the interval.sum_total — the total sum of the elements in the range.indicator — flag that tells us whether sum_max=sum_total. That is, the whole interval is the one with maximum sum.Obviously, for leaf nodes indicator=true and sum_right=sum_left=sum_max=sum_total=[The current element in the array].For non-leaf nodes:sum_left=(left child).sum_leftif (left child).indicator=true, then sum_left+=(right child).sum_leftsum_right=(right child).sum_rightif (right child).indicator=true, then sum_right+=(left child).sum_rightsum_total=(left child).sum_total + (right child).sum_totalsum_max=max((left node).sum_max,(right node).sum_max,sum_left,sum_right,sum_total,(left node).sum_right+(right node).sum_left)My code is here.
•  » » 5 years ago, # ^ |   0 Thanks for your reply! Can you explain what is meant by this " Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } "
•  » » » 5 years ago, # ^ |   +8 It means the maximum sum of consecutive elements from the interval [x;y].For example, let's take the array 1,2,3,-100,5.Query(1;5) = 6 (1+2+3).Query(3;5) = 5 (5).Query(4;4) = -100 (-100).
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Now, completely understood,question statement and reason why we apply segment tree not kadane algo. Thanks for your help :D!
•  » » » » » 4 years ago, # ^ |   0 Will cause TLE.