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.

Odlo

How could it solve it in O(log(n)) time if there are n elements? You have to read them all in which takes O(n) time. – Auschwitz

I meant that the query can be answered in O(log(n)) time. – Odlo

So, would the queries be something along the lines of "what is the largest sum subarray located entirely within this range?" – Garaway

Yes, if we give queries : Left and right. We need to find the largest sum subarray strictly in that range. – Odlo

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.

Segment

O(n log(n)) query time does not satisfy the requirement of the question; he wanted a segment tree with O(log n) queries. A query on your segment tree is essentially worse than the O(n) approach. – Elman

@Elman time per query is O(log(n)), time for O(n log(n)) is a bound for a time needed to insert all n elements in the segment tree – Segment

could you elaborate on how to calculate the 3 values? when you say maximum continuous sum adjacent to the left bound of range corresponding to v's subtree do you mean the maximum sum in v's left subtree and correspondingly the right subtree for right_value? – Binomial

No, let [a, b] be the range corresponding to v's subtree. Then left_value[v] is the maximum-sum prefix in this range i.e. a range [a, i] where a <= i <= b for which the sum is maximal. Does it answer your question? – Segment

Nope I still don't get it. What would right_value and max_value store then? – Binomial

@AbhyudayaSrinet I gave all 3 definitions – Segment

ok I understood what values they store but I can't figure out the code that would calculate them and how I would get my answer using the query. – Binomial

It is not enough to store only these three values. There is just not enough data to combine a node from two sub trees. You can refer this value "Maximum/minimum subvector sum" here wcipeg.com/wiki/Segment_tree – Schick

@AlexLop. Of course it is enough, however, I omitted some details, like storying how far maximum sum adjacent to left/right bound of range is – Segment

Answer 2

While @pkacprzak's answer describes the solution well, some people might prefer a code example.

#include <iostream>
#define ll long long
using namespace std;
const int N=1<<17; // big power of 2 that fits your data

int n,k;
struct P {ll l, r, ts, bs;}; // left, right, totalsum, bestsum
P p[2*N];

ll maxf(ll a,ll b,ll c) {return max(a,max(b,c));}

P combine(P &cl,P &cr) {
  P node;
  node.ts = cl.ts + cr.ts;
  node.l = maxf(cl.l, cl.ts, cl.ts + cr.l);
  node.r = maxf(cr.r, cr.ts, cr.ts + cl.r);
  node.bs = maxf(cl.bs, cr.bs, cl.r + cr.l);
  return node;
}

void change(int k, ll x) {
  k += N;
  p[k].l = p[k].r = p[k].ts = p[k].bs = x;
  for (k /= 2; k >= 1; k /= 2) {
    p[k] = combine(p[2*k], p[2*k+1]);
  }
}

To add/change values in the segment tree use change(k, x) (O(log(n)) per call) where k is the position and x is the value. The maximum subarray's sum can be read from p[1].bs (top of the tree) after each call to change.

If you also need to find the exact indices of the subarray, you can do a recursive top-down query in O(log(n)) or a binary search of O(log^2(n)) with an iterative query.

EDIT: if we are interested in the maximum subarray of a given subarray, it's best to build a recursive top-down query. See:

https://www.quora.com/How-do-I-calculate-the-maximum-sub-segment-sum-in-a-segment-tree

So to recap, segment trees can handle this problem with changes to the data and with changes to the range we are interested in.

Pointenoire