The longest almost-increasing subsequence

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.