2008.11.24 | Else Magård

Title: Selecting Sums in Arrays

Speaker: Allan Grønlund Jørgensen, Aarhus University, MADALGO

Abstract:

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 sumsamong 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 and obtain an $O(n\\cdot \\max\\{1,\\log (k/n)\\})$ time algorithm that selects a subarray storing the $k$'th largest sum among all subarrays of length at least $l$ and at most $u$.

Joint Work with Gerth Stølting Brodal.

Host: Gerth Stølting Brodal