(sequence)
return ans
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
    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 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
def longest_increasing_subsequence_optimized(sequence):
    """
    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
    """
    mx = max(sequence)
    tree = [0] * (mx<<2)

    def update(p, l, r, i, v):
        if l == r:
            tree[p] = v
            return
        mid = (l+r)>>1
        if i <= mid:
            update(p<<1, l, mid, i, v)
        else:
            update((p<<1)|1, mid+1, r, i, v)
        tree[p] = max(tree[p<<1], tree[(p<<1)|1])

    def get_max(p, l, r, s, e):
        if l > e or r < s:
            return 0
        if l >= s and r <= e:
            return tree[p]
        mid = (l+r)>>1
        return max(get_max(p<<1, l, mid, s, e), get_max((p<<1)|1, mid+1, r, s, e))
    ans = 0
    for x in sequence:
       cur = get_max(1, 0, mx, 0, x-1)+1
       ans = max(ans, cur)
       update(1, 0, mx, x, cur)
    return ans
def longest_increasing_subsequence_optimized ( sequence ) : mx = max ( sequence ) tree = [ 0 ] * ( mx << 2 ) def update ( p , l , r , i , v ) : if l == r : tree [ p ] = v return mid = ( l + r ) >> 1 if i <= mid : update ( p << 1 , l , mid , i , v ) else : update ( ( p << 1 ) | 1 , mid + 1 , r , i , v ) tree [ p ] = max ( tree [ p << 1 ] , tree [ ( p << 1 ) | 1 ] ) def get_max ( p , l , r , s , e ) : if l > e or r < s : return 0 if l >= s and r <= e : return tree [ p ] mid = ( l + r ) >> 1 return max ( get_max ( p << 1 , l , mid , s , e ) , get_max ( ( p << 1 ) | 1 , mid + 1 , r , s , e ) ) ans = 0 for x in sequence : cur = get_max ( 1 , 0 , mx , 0 , x - 1 ) + 1 ans = max ( ans , cur ) update ( 1 , 0 , mx , x , cur ) return ans