given an unsorted array of integers find the length of longest increasing subsequence example input 10 9 2 5 3 7 101 18 output 4 explanation the longest increasing subsequence is 2 3 7 101 therefore the length is 4 time complexity first algorithm is on2 second algorithm is onlogx where x is the max element in the list third algorithm is onlogn space complexity first algorithm is on second algorithm is ox where x is the max element in the list third algorithm is on dynamic programming algorithm for counting the length of longest increasing subsequence type sequence listint rtype int optimized dynamic programming algorithm for couting the length of the longest increasing subsequence using segment tree data structure to achieve better complexity if max element is larger than 105 then use longestincreasingsubsequenceoptimied2 instead type sequence listint rtype int optimized dynamic programming algorithm for counting the length of the longest increasing subsequence using segment tree data structure to achieve better complexity type sequence listint rtype int dynamic programming algorithm for counting the length of longest increasing subsequence type sequence list int rtype int optimized dynamic programming algorithm for couting the length of the longest increasing subsequence using segment tree data structure to achieve better complexity if max element is larger than 10 5 then use longest_increasing_subsequence_optimied2 instead type sequence list int rtype int optimized dynamic programming algorithm for counting the length of the longest increasing subsequence using segment tree data structure to achieve better complexity type sequence list int rtype int
def longest_increasing_subsequence(sequence):
    
    length = len(sequence)
    counts = [1 for _ in range(length)]
    for i in range(1, length):
        for j in range(0, i):
            if sequence[i] > sequence[j]:
                counts[i] = max(counts[i], counts[j] + 1)
                print(counts)
    return max(counts)


def longest_increasing_subsequence_optimized(sequence):
    
    max_seq = max(sequence)
    tree = [0] * (max_seq<<2)

    def update(pos, left, right, target, vertex):
        if left == right:
            tree[pos] = vertex
            return
        mid = (left+right)>>1
        if target <= mid:
            update(pos<<1, left, mid, target, vertex)
        else:
            update((pos<<1)|1, mid+1, right, target, vertex)
        tree[pos] = max_seq(tree[pos<<1], tree[(pos<<1)|1])

    def get_max(pos, left, right, start, end):
        if left > end or right < start:
            return 0
        if left >= start and right <= end:
            return tree[pos]
        mid = (left+right)>>1
        return max_seq(get_max(pos<<1, left, mid, start, end),
            get_max((pos<<1)|1, mid+1, right, start, end))
    ans = 0
    for element in sequence:
        cur = get_max(1, 0, max_seq, 0, element-1)+1
        ans = max_seq(ans, cur)
        update(1, 0, max_seq, element, cur)
    return ans


def longest_increasing_subsequence_optimized2(sequence):
    
    length = len(sequence)
    tree = [0] * (length<<2)
    sorted_seq = sorted((x, -i) for i, x in enumerate(sequence))
    def update(pos, left, right, target, vertex):
        if left == right:
            tree[pos] = vertex
            return
        mid = (left+right)>>1
        if target <= mid:
            vertex(pos<<1, left, mid, target, vertex)
        else:
            vertex((pos<<1)|1, mid+1, right, target, vertex)
        tree[pos] = max(tree[pos<<1], tree[(pos<<1)|1])

    def get_max(pos, left, right, start, end):
        if left > end or right < start:
            return 0
        if left >= start and right <= end:
            return tree[pos]
        mid = (left+right)>>1
        return max(get_max(pos<<1, left, mid, start, end),
            get_max((pos<<1)|1, mid+1, right, start, end))
    ans = 0
    for tup in sorted_seq:
        i = -tup[1]
        cur = get_max(1, 0, length-1, 0, i-1)+1
        ans = max(ans, cur)
        update(1, 0, length-1, i, cur)
    return ans