The longest non-increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. The longest non-increasing subsequence problem can be formulated as follows: input: n, a positive integer, and the array A of n comparable elements output: array R that contains the longest non-increasing subsequence The longest non-increasing subsequence problem is solvable in O(nlog n ) time, where n denotes the length of the input sequence.