## Præsentere Artiklen, Selecting Sums in Arrays

Aktivitet: Tale eller præsentation - typerForedrag og mundtlige bidrag

Allan Grønlund - Foredragsholder

• Datalogisk Institut
In an array of $n$ numbers each of the $\binom{n}{2}+n$ contiguous
subarrays define a sum.  In this paper we focus on algorithms for
selecting and reporting maximal sums from an array of numbers. First,
we consider the problem of reporting $k$ subarrays inducing the $k$
largest sums among all subarrays of length at least $l$ and at most
$u$. For this problem we design an optimal $O(n+k)$ time algorithm.
Secondly, we consider the problem of selecting a subarray storing the
$k$'th largest sum. For this problem we prove a time bound of
$\Theta(n \cdot \max\{1,\log k/n\})$ by describing an algorithm with this
running time and by proving a matching lower bound.  Finally, we
combine the ideas we used and obtain an $O(n\cdot \max\{1,\log k/n\})$ time
algorithm for selecting a subarray storing the $k$'th largest sum
among all subarrays of length at least $l$ and at most $u$.

Emneord: Algorithms, Data Structures
15 dec. 2008

### Begivenhed (Konference)

Titel Symposium on Algorithms and Computation 15/12/2008 → 15/12/2008 Algorithms and Data Structures Gold Coast Australien

ID: 14696241