Find the largest sum subarray from the given array using segment trees

Question

I wanted to find the largest sum continuous subarray from the given array. I know the O(n) approach of finding the largest sum continuous subarray approach using the concept of dynamic programming using Kadane's algorithm.

But it will take a lot of time if the no of range queries are very large. Is there a way to solve it using Segment-Trees as it is the best option preferred to answer range queries which it solves in O(log(n)) time. Thank you.

Answer 1

According to my comment to Justin's answer, you can augment a standard segment tree to achieve a O(log(n)) query time with O(n log(n)) time to build the tree i.e. to insert all n elements into the tree.

The idea is to store in every node v not just one value, but four:

1. max_value[v] := maximum continuous sum in v`s subtree
2. left_value[v] := maximum continuous sum adjacent to the left bound of range corresponding to v's subtree
3. right_value[v] := maximum continuous sum adjacent to the right bound of range corresponding to v's subtree
4. sum[v] := the sum of all elements in v's subtree

In order to perform an update operation for a node v, you have to recompute max_value[v], left_value[v], right_value[v], sum[v]. This is very straightforward and I think you can figure it out by yourself - there are a few cases to consider.

A query operation is similar to a query operation in a basic segment tree. The only difference is that in this case, you have to consider also the left_value[v] and the right_value[v] while computing a result - again, there are a few easy cases to consider.

I hope that you'll figure out omitted details. If not, let me know and I'll give a more detailed explanation.