simple segment tree with merging nodes

This problem can be solved using a segment tree.

To understand the solution, you can try to find the Maximum Sub Array Sum in a recursive divide & conquer approach. Once you have a d&c solution (that should have linear time), we can use that to mantain a segmentree containing all the needed information for each interval.

Hint : you might also need to save information about prefix/suffix of the interval you are recurring on :)

There is the same problem on SPOJ

There is my solution

1) Use Segment Tree (if you don't know it, solve some easy problems on segment tree previously)

2) Each node of the Segment Tree will contain 4 numbers:

sum — sum of all numbers of this segment

maxprefix — maximum sum of the prefix on this segment

maxsuffix — maximum sum of the suffix on this segment

maxsum — maximum sibarray sum on this segment

Combine function will be easy:

1) sum = left.sum + right.sum

2) maxprefix = max(left.maxprefix, left.sum+right.maxprefix)

3) maxsuffix = max(left.maxsuffix + right.sum, right.maxsuffix)

4) maxsum = max(left.maxsum, right.maxsum, left.suffix+right.prefix)