dynamic_programming.longest_increasing_subsequence

Author : Mehdi ALAOUI

This is a pure Python implementation of Dynamic Programming solution to the longest increasing subsequence of a given sequence.

The problem is:

Given an array, to find the longest and increasing sub-array in that given array and return it.

Example:

[10, 22, 9, 33, 21, 50, 41, 60, 80] as input will return [10, 22, 33, 41, 60, 80] as output

Functions

longest_subsequence(→ list[int])

Some examples

Module Contents

dynamic_programming.longest_increasing_subsequence.longest_subsequence(array: list[int]) → list[int]

Some examples

>>> longest_subsequence([10, 22, 9, 33, 21, 50, 41, 60, 80])
[10, 22, 33, 41, 60, 80]
>>> longest_subsequence([4, 8, 7, 5, 1, 12, 2, 3, 9])
[1, 2, 3, 9]
>>> longest_subsequence([28, 26, 12, 23, 35, 39])
[12, 23, 35, 39]
>>> longest_subsequence([9, 8, 7, 6, 5, 7])
[5, 7]
>>> longest_subsequence([1, 1, 1])
[1, 1, 1]
>>> longest_subsequence([])
[]