An increasing subsequence of a permutation is a subsequence of the permutation whose elements increase. For example, given the permutation (8, 2, 1, 6, 5, 7, 4, 3, 9), the subsequences (1, 5, 7) and (2, 6, 7, 9) are increasing. (8, 7, 3) is a decreasing permutation subsequence, whereas (2, 6, 4, 9) is neither increasing nor decreasing. You may verify that (2, 6, 7, 9) is an increasing subsequence of maximum length, as is (1, 5, 7, 9).
A longest increasing subsequence of a permutation has a (minor) biological application in that it can be used to represent the largest number of genes on one chromosome that appear in the same order on another chromosome.
