2011 | OriginalPaper | Buchkapitel
Finding Maximum Sum Segments in Sequences with Uncertainty
verfasst von : Hung-I Yu, 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
In this paper, we propose to study the famous
maximum sum segment
problem on a sequence consisting of
n
uncertain numbers, where each number is given as an interval characterizing its possible value. Given two integers
L
and
U
, a segment of length between
L
and
U
is called a
potential maximum sum segment
if there exists a possible assignment of the uncertain numbers such that, under the assignment, the segment has maximum sum over all segments of length between
L
and
U
. We define the
maximum sum segment with uncertainty
problem, which consists of two sub-problems: (1) reporting all potential maximum sum segments; (2) counting the total number of those segments. For
L
= 1 and
U
=
n
, we propose an
O
(
n
+
K
)-time algorithm and an
O
(
n
)-time algorithm, respectively, where
K
is the number of potential maximum sum segments. For general
L
and
U
, we give an
O
(
n
(
U
−
L
))-time algorithm for either problem.