vsanjay_nitdgp's blog

SPOJ-GSS1
By vsanjay_nitdgp, history, 8 years ago, In English

Hello,

could anyone provide good source for understand and solving GSS1 of spoj.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

You better knew how to use Interval Tree before to solve this. At each node K of the IT we will need 4 values: 1. sum: sum of all elements in the interval managed by node K 2. left: the maximum continuous sum starts from the left (prefix sum) of the interval managed by node K 3. right: the maximum continuous sum starts from the right (suffix sum) of the interval managed by node K 4. res: maximum sum of the interval managed by node K (that's it, the answer we need)

When we combine two intervals: - New.sum = L.sum + R.sum - New.left = max(L.left , L.sum + R.left) - New.right = max(R.right , L.right + R.sum) - New.res = max(L.res , R.res , L.right + R.left)

Hope it will help you.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In this page you can find awesome solution and explanation for SPOJ's GSS1 and here discussion for it and also many other problems solved using segment tree and it's variations.

→ Reply