Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Randomized Algorithm for the Sum Selection Problem
verfasst von : Tien-Ching Lin, D. T. Lee
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given a sequence of
n
real numbers
A
=
a
1
,
a
2
,...,
a
n
and a positive integer
k
, the
Sum Selection Problem
is to find the segment
A
(
i
,
j
) =
a
i
,
a
i
+ 1
,...,
a
j
such that the rank of the sum
$s(i, j) = \sum_{t = i}^{j}{a_{t}}$
is
k
over all
${n(n-1)} \over {2}$
segments. We will give a randomized algorithm for this problem that runs in expected
O
(
n
log
n
) time. Applying this algorithm we can obtain an algorithm for the
k
Maximum Sums Problem
, i.e., the problem of enumerating the
k
largest sum segments, that runs in expected
O
(
n
log
n
+
k
) time. The previously best known algorithm for the
k
Maximum Sums Problem
runs in
O
(
n
log
2
n
+
k
) time in the worst case.