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

13
votes

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.

2
arraysalgorithmsegment-tree
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. – Jason
I meant that the query can be answered in O(log(n)) time. – user1580096
So, would the queries be something along the lines of "what is the largest sum subarray located entirely within this range?" – Dennis Meng
Yes, if we give queries : Left and right. We need to find the largest sum subarray strictly in that range. – user1580096

2 Answers

8
votes

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.

1
votes

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.