# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Encodings of Range Maximum-Sum Segment Queries and Applications

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1410.2847.pdf

(Preprint), 488KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Gawrychowski, P., & Nicholson, P. K. (2014). Encodings of Range Maximum-Sum Segment Queries and Applications. Retrieved from http://arxiv.org/abs/1410.2847.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-4465-5

##### Abstract

Given an array A containing arbitrary (positive and negative) numbers, we
consider the problem of supporting range maximum-sum segment queries on A:
i.e., given an arbitrary range [i,j], return the subrange [i' ,j' ] \subseteq
[i,j] such that the sum of the numbers in A[i'..j'] is maximized. Chen and Chao
[Disc. App. Math. 2007] presented a data structure for this problem that
occupies {\Theta}(n) words, can be constructed in {\Theta}(n) time, and
supports queries in {\Theta}(1) time. Our first result is that if only the
indices [i',j'] are desired (rather than the maximum sum achieved in that
subrange), then it is possible to reduce the space to {\Theta}(n) bits,
regardless the numbers stored in A, while retaining the same construction and
query time. We also improve the best known space lower bound for any data
structure that supports range maximum-sum segment queries from n bits to
1.89113n - {\Theta}(lg n) bits, for sufficiently large values of n. Finally, we
provide a new application of this data structure which simplifies a previously
known linear time algorithm for finding k-covers: i.e., given an array A of n
numbers and a number k, find k disjoint subranges [i_1 ,j_1 ],...,[i_k ,j_k ],
such that the total sum of all the numbers in the subranges is maximized.