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
Neste artigo, abordamos os seguintes problemas: Dada uma sequência A of n números reais e quatro parâmetros I,J,X e Y fazendo o melhor dos nossos I≤ J e X≤ Y, encontre a subsequência mais longa (ou mais curta) de A tal que seu comprimento esteja entre I e J e sua soma está entre X e Y. Apresentamos um algoritmo online e um offline para os problemas, ambos executados em O(nlog n) tempo, que são ótimos.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -