Optimal Online and Offline Algorithms for Finding Longest and Shortest Subsequences with Length and Sum Constraints
スポンサーリンク
概要
- 論文の詳細を見る
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(n log n) time, which are optimal.
- （社）電子情報通信学会の論文
- 2010-02-01
著者
-
Kim Sung
School Of Computer Science And Engineering Chung-ang University
-
Kim Sung
School Of Computer Sci. And Engineering Chung-ang Univ.
関連論文
- Alteration of Acetaminophen Metabolism by Sulfate and Steroids in Primary Monolayer Hepatocyte Cultures of Rats and Mice
- Forward Link Performance of Combined Soft and Hard Handoff in Multimedia CDMA Systems
- Pt and RuO_2 Bottom Electrode Effects on Pb(Zr,Ti)O_3 Memory Capacitors
- Optimum Modeling of 3-D Circular Braided Composites
- Characteristics of intermixed InGaAs/InGaAsP Multi-Quantum-Well Structure
- Intermixing Characteristics of Strained-InGaAs/InGaAsP Multiple Quantum Well Structure Using Impurity-Free Vacancy Diffusion
- Study of Prominence Detection Based on Various Phone-Specific Features
- Optimal Online and Offline Algorithms for Finding Longest and Shortest Subsequences with Length and Sum Constraints
- Optimal Algorithms for Finding the Longest Path with Length and Sum Constraints in a Tree
- Optimal Algorithms for Finding Density-Constrained Longest and Heaviest Paths in a Tree