Indexing Range Maximum-Sum Segment Queries with Offsets

Given an array $X$ of real numbers, the maximum-sum segment (MSS) problem is to find an interval $[i,j]$ within $X$ that maximizes the sum of its elements, which we call an MSS of the sequence. This problem found applications, among others, in image processing [11], pattern recognition [19], and biological sequence analysis [26].

The textbook algorithm for solving the MSS problem is Kadane’s algorithm, cf. [10, 4.4 Maximum Subarray Sum]. Since the various applications often require adaptations to specific problem variations, it is not surprising that the MSS problem has been studied in various settings, cf. [6] for an encyclopedic survey of MSS and its variations. Chen and Chao [7] considered an indexing problem, where it is allowed to preprocess $X$ and then answer queries on intervals of $X$. For that task, they devised a linear-time constructible data structure that supports constant-time queries of an MSS for any query interval. They also showed that this problem is linearly equivalent to the range-minimum query (RMQ) problem, meaning that a data structure with construction time $t_c(n)$ and query time $t_q(n)$ solving the MSS problem can be transformed into a data structure solving RMQs with the time complexities $t_c(cn)$ and $t_q(cn)$ for some constant $c$, respectively. Gawrychowski and Nicholson [12] gave a $\mathrm{\Theta }(n)$-bits data structure that also achieves constant query times in the setting that the answer is only the interval and not the maximum sum itself. They also show that $1.89113n-\mathrm{\Theta }(\log n)$ bits are necessary for supporting this query type.

A maximal local MSS is a local MSS that is not a segment of any local MSS other than it, where a local MSS is a segment that has itself as its only MSS. Ruzzo and Tompa [21] gave an algorithm that finds all distinct maximal local MSSs in $O(n)$ time, and Sakai [22] designed a linear-time constructible data structure supporting constant-time queries of the maximal local MSS of any given segment that contains any given position.

Bengtsson and Chen [3] showed that an arbitrarily given number of non-overlapping segments that maximize the sum of all their elements can be found in linear time. Yu et al. [28] considered the MSS problem where each element of the input sequence is uncertain within a specific interval and proposed a linear-time algorithm for this problem. The density of a segment is defined as the mean of all elements in the segment. Cheng et al. [8] considered the MSS problem with the condition that the density of the segment to be found is between given lower and upper bounds. Bae [1] and Liu and Chao [17] considering returning $k$ non-overlapping segments that maximize the sum of all their elements.

Another variant is the maximum-density segment query [16, 13, 15] that asks to find a segment of length between a given lower and upper bound that maximizes the density. Chung and Lu [9] showed that this query is solvable in linear time.

Another natural extension of the one-dimensional maximum segment sum problem is the maximum subarray problem, where the input is a two-dimensional array with length $n$ in each dimension, and the goal is to find a contiguous rectangular subarray that has the largest sum. This problem has been addressed by Bentley [4], who gave an $O(n^3)$-time algorithm for the problem. Subsequently, the time complexity has been improved to $O(n^3\sqrt{\log \log n/\log n})$ by Takaoka [24] and further to $O(n^3\log \log n/\log n)$ by Tamaki and Tokuyama [25]. They showed that the problem can be reducible to $(\min ,+)$-matrix multiplication. Using this result, the current fastest algorithm runs in $n^3/2^{\mathrm{\Omega }{(\log n)}^{1/2}}$ time by Chan and Williams [5], which also applies to higher-dimensional arrays. In addition, Fukuda et al. [11] introduced the maximum convex sum problem, which is a variant of the maximum subarray problem where the retrieved subarray must be convex (i.e., the intersection of the subarray with any row or column is connected). Here, Bae and Takaoka [2] gave an $O(n)$-time parallel algorithm solving the maximum convex sum problem for $n^2$ processors.

Our computation model is the RAM model. Let $ℝ$ denote the set of all real numbers. We write $[i,j]=\{i,i+1,i+2,\mathrm{\dots },j\}$ for two integers $i\le j$, and use the same notation $[i,j]$ for intervals of real numbers in case that $i,j\in ℝ$. We assume that all real numbers can be stored in a single word and that basic arithmetic operations on these numbers can be performed in constant time. (We also assume that there are no errors in computational precision due to rounding or overflow.)

Let $X_0[1..n]$ be the input array of real numbers. $X_0$ is subject to the following queries, for which we present examples in Figure 1. While the queries are initially stated to return the value of a specific subarray of $X_0$, it is beneficial to also return the interval of the subarray that gives the answer, which we call the answer range. Since we here mostly focus on data structures using $\mathrm{\Omega }(n)$ space, it suffices to focus on finding answer ranges – we will shortly later see that the actual value can be obtained from an answer range with an $O(n)$-space array of prefix sums. We state our base problem as follows.

We also study the special case that the answer range of the MSS problem is constrained to be a suffix of $X_0$.

Sakai [23] introduced the following indexing problem that generalizes the MSS problem by allowing a query offset parameter $\alpha$ to be subtracted from all array entries before answering the query.

Defining the array $X_{\alpha }[1..n]$ with $X_{\alpha }[i]:=X_0[i]-\alpha$, the OMSS query on $X_0$ with offset $\alpha$ is the MSS query on $X_{\alpha }$. Hence, OMSS is a generalization of MSS, since the answer to an MSS query on $X_0$ is the same as the answer to an OMSS query on $X_{\alpha }$ with offset $\alpha =0$. Sakai [23] presented an approach answering an OMSS query as follows.

The predecessor of $\alpha$ in $L$ is the largest offset in $L$ that is smaller than or equal to $\alpha$. Three observations are in order regarding Lemma 1.

First, while the list of Lemma 1 does not explicitly return the MSS for a query offset $\alpha$, we can compute the sum ${\sum }_{i=a}^b(X_0[i]-\alpha )$ for an entry $(\alpha ,[a..b])$ in $L$ in constant time if we have the array of prefix lengths $C_0[1..n]$ of $X_0$, where $C_0[i]:={\sum }_{k=1}^i{X}_0[k]$ for each $i\in [1,n]$. To see that, define the prefix sum of $X_{\alpha }$ for each $i\in [1,n]$ as $C_{\alpha }[i]:={\sum }_{k=1}^i{X}_{\alpha }[k]=C_0[i]-\alpha k$, and the sum of the subarray $X_{\alpha }[i..j]$ as $S_{\alpha }(i,j)={\sum }_{k=i}^j{X}_{\alpha }[k]=C_0[j]-C_0[i-1]-\alpha (j-i+1)$ for any $i$ and $j$ with $1\le i\le j\le n$. Then ${\sum }_{i=a}^b(X_0[i]-\alpha )=S_{\alpha }(a,b)$.

Second, the upper bound $|L|\le n$ is tight since $L$ can reach the size $n$ for the input $X_0=[1,2,3,\mathrm{\dots },n]$, where the OMSS query for $\alpha =k+ϵ$ gives the range $[k+1,n]$ for every $ϵ\in (0,1)$ and $k\in [0,n]$.

Finally, there can be multiple answer ranges for a query, in particular if the interval covers trailing zeros (after applying the offset). While implicit, the intervals of Lemma 1 do not contain any zero-sum suffix nor prefix.

Now we present our main problem of interest, which combines the OMSS and MSS queries on subarrays of $X_0$.

Using the notation of $S_{\alpha }(i,j)$, the answer to an R-OMSS query on $X_0$ with query range $[a,b]$ and offset $\alpha$ can be computed as ${\max }_{[\mathrm{\ell },r]\subseteq [a,b]}{S}_{\alpha }(\mathrm{\ell },r)$. The R-OMSS is a generalization of the OMSS problem (with the query range $[1,n]$) and the range MSS problem introduced by Chen et al. [7], which asks for the MSS of a query range $[a,b]$ without the offset parameter (i.e., $\alpha =0$). Like for MSS and its restriction SMSS, we can also define the suffix and prefix versions of R-OMSS queries, where the answer range is constrained to be a suffix or a prefix of the query range, respectively.

A symmetric definition can be given for prefix R-OMSS queries, where the answer range is constrained to be a prefix of the query range.

Our main goal of this paper is to devise data structures for answering R-OMSS queries on $X_0$, where a non-negative offset $\alpha \ge 0$ and a query range $[a,b]$ are given at query time. There are two naive approaches prioritizing either (1) space or (2) time.

1. (1)

   We can apply Kadane’s algorithm on $X_{\alpha }[a..b]$. Since any value in $X_{\alpha }$ can be computed in $O(1)$ time from $X_0$, Kadane’s algorithm answers R-OMSS in $O(n)$ time using $O(1)$ space additional to $X_0$.

2. (2)

   Alternatively, we can maintain the data structure of Lemma 1 for all $\mathrm{\Theta }(n^2)$ possible query ranges. This results in an $O(n^3)$-space data structure with $O(\log n)$ query time.

In what follows, we present two non-trivial data structures for R-OMSS queries that finds its complexities between the solutions (1) and (2). We start with an $O(n)$-space data structure answering suffix R-OMSS queries on $X_0$ in $O({\log }^{2}n)$ time. By symmetry, the same data structure results can be obtained for prefix R-OMSS queries. Next, in Section 3.2, we consider a data structure for (general) R-OMSS queries. By combining the data structure of Lemma 1 with the suffix R-OMSS data structures, we obtain an $O(n\log n)$-space data structure that can answer an R-OMSS query in $O({\log }^{2}n)$ time.

Based on the results of the previous section, we analyze and devise specializations of our data structures for R-OMSS queries on $X_0$ under special input types. Specifically, we consider the following three scenarios: (1) the offset $\alpha$ is restricted to positive integers, (2) $X_0$ is an array over an alphabet of size $\sigma$, and (3) $X_0$ is given in run-length encoded (RLE) form.