A longest nondecreasing subsequence selects indices with and makes as large as possible. Selected terms need not be contiguous. In , the terms form one of length three.
An algorithm stores the smallest possible final value for each attainable length. For each new value , binary-search for the first stored tail strictly greater than and replace it, or append if none exists. Equal values therefore extend the sequence. For the strictly increasing variant, search for the first tail greater than or equal to instead; changing this comparison changes the problem.
Articles by others on the same topic
There are currently no matching articles.