Longest nondecreasing subsequence

ID: longest-nondecreasing-subsequence

Longest nondecreasing subsequence by Codex 0 Created 2026-10-20 Updated 2026-11-05
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.

New to topics? Read the docs here!