Longest Increasing Subsequence

https://img.shields.io/pypi/v/longest_increasing_subsequence.svg https://travis-ci.com/mCodingLLC/longest_increasing_subsequence.svg?branch=master Documentation Status

Find the longest increasing or decreasing subsequence of a sequence.

Install with:

pip install longest-increasing-subsequence

Usage:

from longest_increasing_subsequence import (longest_increasing_subsequence,
                                            longest_decreasing_subsequence,
                                            longest_increasing_subsequence_indices)

longest_increasing_subsequence([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])
# [0, 2, 6, 9, 11, 15]

longest_increasing_subsequence([0, 0, 1, 2, 3, 2, 1, 0, 0])
# [0, 0, 1, 2, 2]

longest_decreasing_subsequence([0, 0, 1, 2, 3, 2, 1, 0, 0])
# [3, 2, 1, 0, 0]

longest_increasing_subsequence([0, 0, 1, 2, 3], strict=True)
# [0, 1, 2, 3]

longest_increasing_subsequence(['A', 'B', 'CC', 'D', 'EEE'], key=len)
# ['A', 'B', 'D', 'EEE']

"".join(longest_increasing_subsequence('aababbbdccddd'))
# 'aaabbbccddd'

longest_increasing_subsequence_indices([0, 0, 1, 2, 3, 2, 1, 0, 0])
# [0, 1, 2, 3, 5]

Features

  • Works with arbitrary sequence types (list, tuple, str, numpy array, pandas series, etc.)

  • Works with arbitrary comparable elements (anything that has < and >).

  • Can compute increasing or decreasing subsequences.

  • Can compute strictly increasing or strictly decreasing subsequences.

  • Can compare elements by an optional key function (e.g. compare strings by length).

  • Can return the subsequence or the indices of the subsequence.

Credits

This package was created with Cookiecutter and the audreyr/cookiecutter-pypackage project template.