SPOJ - GSS1

Considering input series: { 4 , -10 , 3 , 100 , -20 , 1 }
Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }

A node contains- 
[ START & END is a node's segment limit ]
Prefix is the maximum sum starting at START, end can be anywhere. There are two possibilities of the maximum. One, node's leftChild's prefix or two, adding leftChild's sum + rightChild's prefix. (which will make the prefix contiguous)
Suffix is the maximum sum ending at END, start can be anywhere.
There's two possibility of the maximum. One, node's rightChild's already calculated suffix or two, add rightChild's sum + leftChild's suffix (which will make the suffix contiguous).
Sum: leftChild's sum + rightChild's sum.
MAX Maximum of  - 

• prefix (result is in the node, starts from START but doesn't end in END )
• suffix  (result is in the node, doesn't start from START but surely ends in END )
• leftChild's max ( result is in left child completely )
• rightChild's max (result is in right child completely )
• leftChild's suffix + rightChild's prefix ( result is in between leftChild & rightChild )

[ this explains why we need prefix,suffix in a node: to calculate MAX ]

Notice that, in last point, we can't add leftChild's Max + rightChild's Max because in some cases that would result in a non-contiguous MAX. 
Considering sub interval  4 -10  3

• prefix = 4
• suffix = 3
• sum = -3
• best = 4 

considering subinterval 100 -20   1

• prefix =100    leftChild's prefix
• suffix = 81     rightChild's sum + leftChild's suiffx 
• sum =81
• best = 100     prefix from above 

In query function, we'll build a node RESULT to return\.
finally, Query(x,y) = result.MAX ;