Source code for pygorithm.dynamic_programming.lis

"""
Author: Omkar Pathak
Created At: 25th August 2017
"""
import inspect

[docs]def longest_increasing_subsequence(_list): """ The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for [10, 22, 9, 33, 21, 50, 41, 60, 80] is 6 and LIS is [10, 22, 33, 50, 60, 80]. :param _list: an array of elements :return: returns a tuple of maximum length of lis and an array of the elements of lis """ # Initialize list with some value lis = [1] * len(_list) # list for storing the elements in an lis elements = [0] * len(_list) # Compute optimized LIS values in bottom up manner for i in range(1, len(_list)): for j in range(0, i): if _list[i] > _list[j] and lis[i] < lis[j] + 1: lis[i] = lis[j]+1 elements[i] = j # find the maximum of the whole list and get its index in idx maximum = max(lis) idx = lis.index(maximum) # for printing the elements later seq = [_list[idx]] while idx != elements[idx]: idx = elements[idx] seq.append(_list[idx]) return (maximum, seq[::-1])
[docs]def get_code(): """ returns the code for the longest_increasing_subsequence function """ return inspect.getsource(longest_increasing_subsequence)