Journal
INFORMATION PROCESSING LETTERS
Volume 110, Issue 16, Pages 655-658Publisher
ELSEVIER
DOI: 10.1016/j.ipl.2010.05.022
Keywords
Algorithms; Algorithm design and analysis; Data structures
Categories
Ask authors/readers for more resources
Given a sequence of n elements, we introduce the notion of an almost-increasing subsequence as the longest subsequence that can be converted to an increasing subsequence by possibly adding a value, that is at most a fixed constant, to each of the elements. We show how to optimally construct such subsequence in O(n logk) time, where k is the length of the output subsequence. (C) 2010 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available