Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Longest Increasing Subsequences in Windows Based on Canonical Antichain Partition
verfasst von : Erdong Chen, Hao Yuan, Linji Yang
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
We consider the
Lisw
problem, which is to find the longest increasing subsequences (LIS) in a sliding window of fixed-size w over a sequence
π
1
π
2
...
π
n
. Formally, it is to find a LIS for every window in a set
S
FIX
={
π
〈
i
+ 1,
i
+
w
〉|0 ≤
i
≤
n
−
w
} ∪ {
π
〈1,
i
〉,
π
〈
n
−
i
,
n
〉|
i
<
w
}, where a window
π
〈
l
,
r
〉 is a subsequence
π
l
π
l
+ 1
...
π
r
. By maintaining a
canonical antichain partition
in windows, we present an optimal
output-sensitive
algorithm to solve this problem in
O
(
output
) time, where
output
is the sum of the length of the
n
+
w
–1 longest increasing subsequences in those windows of
S
FIX
. In addition, we propose a more generalized problem called
Lisset
, which is to find the LIS for every window in a set
S
VAR
containing
variable-size
windows. By applying our algorithm, we provide an efficient solution for
Lisset
problem which is better than the straight forward generalization of classical LIS algorithms. An upper bound of our algorithm on
Lisset
is discussed.