longest increasing subsequence o(nlogn) Algorithm

The Longest Increasing Subsequence (LIS) O(nlogn) Algorithm is an advanced dynamic programming technique used to find the length of the longest subsequence of a given sequence, such that all elements of the subsequence are sorted in increasing order. This algorithm is significantly faster than the basic dynamic programming approach, which has a time complexity of O(n^2). The O(nlogn) Algorithm is particularly useful in situations where the input sequence is very large, as it reduces the processing time considerably. The key idea behind the O(nlogn) Algorithm is to maintain an active list of potential subsequences while iterating through the input sequence. The active list is updated at each step by either extending an existing subsequence or creating a new one. The algorithm utilizes binary search to efficiently determine the correct position for each element within the active list, thus maintaining the sorted order and ensuring an optimal solution. By the end of the iteration, the length of the longest increasing subsequence can be found as the length of the longest active list. This approach allows the algorithm to solve the problem in O(nlogn) time, making it a powerful tool for handling large sequences.
#############################
# Author: Aravind Kashyap
# File: lis.py
# comments: This programme outputs the Longest Strictly Increasing Subsequence in
#           O(NLogN) Where N is the Number of elements in the list
#############################
from typing import List


def CeilIndex(v, l, r, key):  # noqa: E741
    while r - l > 1:
        m = (l + r) // 2
        if v[m] >= key:
            r = m
        else:
            l = m  # noqa: E741
    return r


def LongestIncreasingSubsequenceLength(v: List[int]) -> int:
    """
    >>> LongestIncreasingSubsequenceLength([2, 5, 3, 7, 11, 8, 10, 13, 6])
    6
    >>> LongestIncreasingSubsequenceLength([])
    0
    >>> LongestIncreasingSubsequenceLength([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3,
    ...                                     11, 7, 15])
    6
    >>> LongestIncreasingSubsequenceLength([5, 4, 3, 2, 1])
    1
    """
    if len(v) == 0:
        return 0

    tail = [0] * len(v)
    length = 1

    tail[0] = v[0]

    for i in range(1, len(v)):
        if v[i] < tail[0]:
            tail[0] = v[i]
        elif v[i] > tail[length - 1]:
            tail[length] = v[i]
            length += 1
        else:
            tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i]

    return length


if __name__ == "__main__":
    import doctest

    doctest.testmod()

LANGUAGE:

DARK MODE: