The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dans cet article, nous abordons les problèmes suivants : Étant donné une séquence A of n nombres réels et quatre paramètres I,J,X et à la Y avec I≤ J et à la X≤ Y, trouvez la sous-séquence la plus longue (ou la plus courte) de A telle que sa longueur soit comprise entre I et à la J et sa somme est comprise entre X et à la Y. Nous présentons un algorithme en ligne et un algorithme hors ligne pour les problèmes, tous deux exécutés en O(nenregistrer n) temps, qui sont optimaux.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Sung Kwon KIM, "Optimal Online and Offline Algorithms for Finding Longest and Shortest Subsequences with Length and Sum Constraints" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 2, pp. 250-256, February 2010, doi: 10.1587/transinf.E93.D.250.
Abstract: In this paper, we address the following problems: Given a sequence A of n real numbers, and four parameters I,J,X and Y with I≤ J and X≤ Y, find the longest (or shortest) subsequence of A such that its length is between I and J and its sum is between X and Y. We present an online and an offline algorithm for the problems, both run in O(nlog n) time, which are optimal.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.250/_p
Copier
@ARTICLE{e93-d_2_250,
author={Sung Kwon KIM, },
journal={IEICE TRANSACTIONS on Information},
title={Optimal Online and Offline Algorithms for Finding Longest and Shortest Subsequences with Length and Sum Constraints},
year={2010},
volume={E93-D},
number={2},
pages={250-256},
abstract={In this paper, we address the following problems: Given a sequence A of n real numbers, and four parameters I,J,X and Y with I≤ J and X≤ Y, find the longest (or shortest) subsequence of A such that its length is between I and J and its sum is between X and Y. We present an online and an offline algorithm for the problems, both run in O(nlog n) time, which are optimal.},
keywords={},
doi={10.1587/transinf.E93.D.250},
ISSN={1745-1361},
month={February},}
Copier
TY - JOUR
TI - Optimal Online and Offline Algorithms for Finding Longest and Shortest Subsequences with Length and Sum Constraints
T2 - IEICE TRANSACTIONS on Information
SP - 250
EP - 256
AU - Sung Kwon KIM
PY - 2010
DO - 10.1587/transinf.E93.D.250
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2010
AB - In this paper, we address the following problems: Given a sequence A of n real numbers, and four parameters I,J,X and Y with I≤ J and X≤ Y, find the longest (or shortest) subsequence of A such that its length is between I and J and its sum is between X and Y. We present an online and an offline algorithm for the problems, both run in O(nlog n) time, which are optimal.
ER -