longest_increasing_subsequence package

Module contents

Top-level package for Longest Increasing Subsequence.

longest_increasing_subsequence.longest_decreasing_subsequence(seq: Sequence[T], strict=False, key: Optional[Callable] = None) → List[T]

Returns the longest decreasing subsequence of the given sequence. There may be other decreasing subsequences of the same length.

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

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

>>> longest_decreasing_subsequence([0, 0, 1, 2, 3, 2, 1, 0, 0], strict=True)
[3, 2, 1, 0]

Parameters

• seq – A sequence-like container of comparable objects.

• strict – Whether the subsequence must be strictly decreasing.

• key – If not None, values in sequence are compared by comparing their keys.

Returns

The longest decreasing subsequence in seq as a list.

longest_increasing_subsequence.longest_decreasing_subsequence_indices(seq: Sequence[T], strict=False, key: Optional[Callable] = None) → List[int]

Returns the indices of the longest decreasing subsequence of the given sequence. There may be other decreasing subsequences of the same length.

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

>>> longest_decreasing_subsequence_indices([0, 0, 1, 2, 3, 2, 1, 0, 0])
[4, 5, 6, 7, 8]

>>> longest_decreasing_subsequence_indices([0, 0, 1, 2, 3, 2, 1, 0, 0], strict=True)
[4, 5, 6, 7]

Parameters

• seq – A sequence-like container of comparable objects.

• strict – Whether the subsequence must be strictly decreasing.

• key – If not None, values in sequence are compared by comparing their keys.

Returns

A list of indices of the longest decreasing subsequence in seq.

longest_increasing_subsequence.longest_increasing_subsequence(seq: Sequence[T], strict=False, key: Optional[Callable] = None) → List[T]

Returns the longest increasing subsequence of the given sequence. There may be other increasing subsequences of the same length.

>>> 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_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'

Parameters

• seq – A sequence-like container of comparable objects.

• strict – Whether the subsequence must be strictly increasing.

• key – If not None, values in sequence are compared by comparing their keys.

Returns

The longest increasing subsequence in seq as a list.

longest_increasing_subsequence.longest_increasing_subsequence_indices(seq: Sequence[T], strict=False, key: Optional[Callable] = None) → List[int]

Returns the indices of the longest increasing subsequence of the given sequence. There may be other increasing subsequences of the same length.

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

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

>>> longest_increasing_subsequence_indices([0, 0, 1, 2, 3, 2, 1, 0, 0], strict=True)
[0, 2, 3, 4]

Parameters

• seq – A sequence-like container of comparable objects.

• strict – Whether the subsequence must be strictly increasing.

• key – If not None, values in sequence are compared by comparing their keys.

Returns

A list of indices of the longest increasing subsequence in seq.