Advertisement
Published in:
2011 | OriginalPaper | Chapter
Finding Maximum Sum Segments in Sequences with Uncertainty
Authors : Hung-I Yu, Tien-Ching Lin, D. T. Lee
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.